数据结构与算法 / 系统课时

主定理

主定理

递归树给出了每层如何计费。对等比例、同规模的分治递推,主定理可以从当前节点工作和叶子规模的比较直接得到紧确阶。关键是先确认适用形式,再检查各情况的条件。

学习目标

  • 写出临界增长率 nlog⁡ban^{\log_b a},检查递推形式和基例。
  • 区分三种情况及其多项式差距、正则条件。
  • 知道何时应回到递归树、代入法或更一般的方法。

先检查递推形式

考虑 T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n)。a≥1a≥1 是固定的子问题数,b>1b>1 是固定的缩小比例,基例成本为 Θ(1)\Theta(1),f(n)f(n) 最终非负。先在规模为 bb 的幂的情形理解判定。涉及整数取整时应核对所用定理版本及实际递推;大小差别很大的两个子问题不能直接凑成这一形式。设 p=log⁡bap=\log_b a,则 alog⁡bn=npa^{\log_b n}=n^p 是等规模树的叶子量级。 MIT 主定理资料 MIT 取整与递推

三种情况

情况 条件 结论
1 存在固定 ε>0ε>0,使 f(n)=O(np−ε)f(n)=O(n^{p-ε}) T(n)=Θ(np)T(n)=\Theta(n^p)
2 f(n)=Θ(nplog⁡kn)f(n)=\Theta(n^p\log^k n),k≥0k≥0 T(n)=Θ(nplog⁡k+1n)T(n)=\Theta(n^p\log^{k+1}n)
3 存在固定 ε>0ε>0,使 f(n)=Ω(np+ε)f(n)=\Omega(n^{p+ε}),并满足正则条件 T(n)=Θ(f(n))T(n)=\Theta(f(n))

这里使用情况 2 包含 k≥0k≥0 的版本。只有 k=0k=0 时,等规模树各内部层的工作都同阶于 npn^p。若 k>0k>0,各层的对数因子会变化。从根到叶的深度为 h=log⁡bnh=\log_b n,去掉共同的 npn^p 后,内部层总和同阶于 ∑j=1hjk\sum_{j=1}^h j^k,即 Θ(hk+1)\Theta(h^{k+1})。 MIT 主定理扩展形式

情况 3 还要求存在固定 0<c<10<c<1,使得充分大的 nn 满足 af(n/b)≤cf(n)af(n/b)≤cf(n)。它约束每下一层非递归成本的衰减。对于精确函数 f(n)=nqlog⁡knf(n)=n^q\log^k n、q>pq>p、k≥0k≥0,当 n>bn>b 时比值至多为 a/bq<1a/b^q<1,因此可取这个常数作为 cc。 MIT 主定理正则条件

主定理三种情况对比

例如 2T(n/2)+12T(n/2)+1 的临界指数为 1,得到 Θ(n)\Theta(n)。换成 2T(n/2)+n2T(n/2)+n 得 Θ(nlog⁡n)\Theta(n\log n)。换成 2T(n/2)+n22T(n/2)+n^2,情况 3 的比值为 1/2,得 Θ(n2)\Theta(n^2)。3T(n/3)+nlog⁡n3T(n/3)+n\log n 则按情况 2 得 Θ(nlog⁡2n)\Theta(n\log^2 n)。

可运行示例:用整数比较临界指数

下面程序只处理精确函数族 f(n)=nqlog⁡knf(n)=n^q\log^k n 中 q,kq,k 为非负整数的样例。若 bq<ab^q<a,则 q<pq<p;若相等,则 q=pq=p;否则 q>pq>p。这个比较不需要把对数取成浮点值。程序返回情况号和结果中的对数指数;结果的 nn 指数按表使用 pp 或 qq。

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

什么时候换方法

不等规模的 T(n/3)+T(2n/3)+nT(n/3)+T(2n/3)+n 和随规模变化的 nT(n/2)+nnT(n/2)+n 不符合这里的形式。f(n)=np/log⁡nf(n)=n^p/\log n 比临界项慢,却没有情况 1 所需的多项式级差距,也不在本课情况 2 的 k≥0k≥0 范围。不能因为更快或更慢就硬套。情况 3 的正则条件若无法证明,也应换用其他推导。 MIT 主定理适用条件

本课练习

用整数比较判定 8T(n/2)+n28T(n/2)+n^2。然后用递归树检查 3T(n/3)+nlog⁡n3T(n/3)+n\log n 的层成本如何变化。下一课把拆分、合并、正确性和递推分析用在同一个问题上。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

主定理

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通