数据结构与算法 / 系统课时
主定理
主定理
递归树给出了每层如何计费。对等比例、同规模的分治递推,主定理可以从当前节点工作和叶子规模的比较直接得到紧确阶。关键是先确认适用形式,再检查各情况的条件。
学习目标
- 写出临界增长率 ,检查递推形式和基例。
- 区分三种情况及其多项式差距、正则条件。
- 知道何时应回到递归树、代入法或更一般的方法。
先检查递推形式
考虑 。 是固定的子问题数, 是固定的缩小比例,基例成本为 , 最终非负。先在规模为 的幂的情形理解判定。涉及整数取整时应核对所用定理版本及实际递推;大小差别很大的两个子问题不能直接凑成这一形式。设 ,则 是等规模树的叶子量级。 MIT 主定理资料 MIT 取整与递推
三种情况
| 情况 | 条件 | 结论 |
|---|---|---|
| 1 | 存在固定 ,使 | |
| 2 | , | |
| 3 | 存在固定 ,使 ,并满足正则条件 |
这里使用情况 2 包含 的版本。只有 时,等规模树各内部层的工作都同阶于 。若 ,各层的对数因子会变化。从根到叶的深度为 ,去掉共同的 后,内部层总和同阶于 ,即 。 MIT 主定理扩展形式
情况 3 还要求存在固定 ,使得充分大的 满足 。它约束每下一层非递归成本的衰减。对于精确函数 、、,当 时比值至多为 ,因此可取这个常数作为 。 MIT 主定理正则条件

例如 的临界指数为 1,得到 。换成 得 。换成 ,情况 3 的比值为 1/2,得 。 则按情况 2 得 。
可运行示例:用整数比较临界指数
下面程序只处理精确函数族 中 为非负整数的样例。若 ,则 ;若相等,则 ;否则 。这个比较不需要把对数取成浮点值。程序返回情况号和结果中的对数指数;结果的 指数按表使用 或 。
python
def classify(a: int, b: int, q: int, k: int = 0) -> tuple[int, int]:
if any(type(value) is not int for value in (a, b, q, k)):
raise ValueError("expected integer parameters")
if a < 1 or b < 2 or q < 0 or k < 0:
raise ValueError("require a >= 1, b >= 2, q >= 0 and k >= 0")
growth = b ** q
if growth < a:
return 1, 0
if growth == a:
return 2, k + 1
return 3, k
for a, b, q, k in [(2, 2, 0, 0), (2, 2, 1, 0), (2, 2, 2, 0),
(3, 3, 1, 1), (3, 2, 1, 0)]:
case, log_power = classify(a, b, q, k)
print(f"{(a, b, q, k)}: case={case}, log power={log_power}")text
(2, 2, 0, 0): case=1, log power=0
(2, 2, 1, 0): case=2, log power=1
(2, 2, 2, 0): case=3, log power=0
(3, 3, 1, 1): case=2, log power=2
(3, 2, 1, 0): case=1, log power=0什么时候换方法
不等规模的 和随规模变化的 不符合这里的形式。 比临界项慢,却没有情况 1 所需的多项式级差距,也不在本课情况 2 的 范围。不能因为更快或更慢就硬套。情况 3 的正则条件若无法证明,也应换用其他推导。 MIT 主定理适用条件
本课练习
用整数比较判定 。然后用递归树检查 的层成本如何变化。下一课把拆分、合并、正确性和递推分析用在同一个问题上。
按自己的节奏,确认真正理解。