4.3 分治递推与主定理：先验证模型，再套结论

主定理能快速求一类分治递推，但它不是看到递归就能使用的复杂度计算器。使用前必须确认子问题数量、缩小比例和当前层成本符合模型。

标准模型

主定理处理：

T(n)=aT(n/b)+f(n)

其中：

• a≥1：子问题个数；
• b>1：每个子问题的规模缩小为约 n/b；
• f(n)：拆分、合并及其他非递归成本。

比较基准：

n^(log_b a)

它近似表示递归树叶子总量带来的成本。

本课先取 n=b^k、基础规模 1、T(1)=Θ(1)，并要求 a,b 为不随 n 改变的常数，f(n) 最终非负。一般整数输入还要明确向上或向下取整及基础阈值；不能从幂次子序列的结论直接跳过这一步。

三种常见情形

情形 1：叶子侧占主导

若存在 ε>0：

f(n)=O(n^(log_b a-ε))

则：

T(n)=Θ(n^(log_b a))

例：

T(n)=8T(n/2)+n²

n^(log₂8)=n³，n² 多项式级更小，所以 T(n)=Θ(n³)。

情形 2：各层大致平衡

标准简化版中，若：

f(n)=Θ(n^(log_b a))

则：

T(n)=Θ(n^(log_b a) log n)

归并排序：

T(n)=2T(n/2)+Θ(n)

基准也是 n，所以 Θ(n log n)。

更一般版本可处理额外的对数因子，但使用时要明确采用哪个版本，不能把不同教材的条件混在一起。

情形 3：根部工作占主导

若存在 ε>0：

f(n)=Ω(n^(log_b a+ε))

并满足正则条件：存在 0<c<1，对充分大的 n：

a f(n/b) ≤ c f(n)

则：

T(n)=Θ(f(n))

例：

T(n)=2T(n/2)+n²

基准为 n，n² 多项式级更大，且正则条件成立，所以 Θ(n²)。

正则条件不能省略，它阻止 f(n) 在不同规模间剧烈振荡，使递归子层总工作确实比当前层按固定比例小。

本例可直接计算 2(n/2)²=n²/2，取 c=1/2 即可。下面的 Python 3 示例固定 T(1)=1，只接受正的 2 次幂；三列依次对应 8T(n/2)+n²、2T(n/2)+n、2T(n/2)+n²：

from functools import cache

@cache
def cost(n, a, exponent):
    if n == 1:
        return 1
    return a * cost(n // 2, a, exponent) + n**exponent

for n in [2, 4, 8]:
    print(n, cost(n, 8, 2), cost(n, 2, 1), cost(n, 2, 2))
# 2 12 4 6
# 4 112 12 28
# 8 960 32 120

三列精确解分别为 2n³−n²、n(1+log₂n)、2n²−n，可直接代回递推验证。数字表负责查算错；渐近结论仍依赖上述一般推导。

三个典型例子

二分查找

以下分析最坏查找路径；若第一次比较就命中，最好情况为 Θ(1)。

T(n)=T(n/2)+Θ(1)

a=1,b=2，基准 n^0=1，属于情形 2：

T(n)=Θ(log n)

归并排序

T(n)=2T(n/2)+Θ(n)

得到 Θ(n log n)。

Strassen 矩阵乘法

T(n)=7T(n/2)+Θ(n²)

基准 n^(log₂7) 约为 n^2.807，大于 n²：

T(n)=Θ(n^(log₂7))

渐近优势不等于所有矩阵规模上都更快；常数、缓存和数值稳定性仍需实测。

主定理不适用的递推

T(n)=T(n-1)+n                 // 子问题不是 n/b
T(n)=T(n/3)+T(2n/3)+n        // 子问题大小不相等
T(n)=2T(n/2)+n log n          // 取决于使用的主定理版本
T(n)=T(√n)+1                  // 缩小形式不同
T(n)=T(n-1)+T(n-2)+1         // Fibonacci 型

这些递推可以用展开、递归树、代入、变量替换、特征方程或 Akra–Bazzi 等工具。不能套主定理不等于无法分析。

例如第三条取 n=2^k，第 j 层成本是 n(k−j)，内部层总成本为 n(k+(k−1)+...+1)=Θ(n log²n)。log n 因子不比 n 的任何固定正幂更快，不能拿它满足情形 3 的多项式差距。

快速排序尤其需要区分情况：

• 最坏划分：T(n)=T(n-1)+Θ(n)=Θ(n²)；
• 理想平衡：2T(n/2)+Θ(n)=Θ(n log n)；
• 随机或平均分析需要概率模型，不能直接把每次划分假定成一半。

从实现确认递推假设

分析合并排序时，若每层都复制整个数组片段，f(n) 可能仍是线性，但空间和常数不同。若语言切片是视图，成本又不同。建立递推前应确认：

• 子问题是否重叠；
• 切片是复制还是视图；
• 合并是否真的线性；
• 输入是否始终平衡；
• 并行执行时衡量的是总工作还是关键路径；
• 基础阈值和混合算法是否改变小规模行为。

递归、记忆化与动态规划

若子问题重叠，直接递归会反复计算。对依赖本来就无环的问题，记忆化按参数共享已完成结果，把展开树中重复的状态合并为 DAG。缓存不会自动消除依赖环：若 f(x) 等待自己尚未完成的结果，需要循环检测、固定点求解或不同模型。记忆化适合：

• 相同参数确实表示相同子问题；
• 结果不依赖隐藏的可变状态；
• 缓存键有稳定相等语义；
• 状态数量可控。

自底向上动态规划按依赖顺序填表，常能避免递归栈并优化空间。两者求解同一递推时复杂度可能相同，但访问顺序和常数不同。

缓存不是免费的：无界记忆化可能把时间问题换成持续内存增长；并发缓存还涉及重复计算、锁竞争和失败结果是否缓存。

一条实用分析流程

1. 选择输入规模 n；
2. 明确基本情况；
3. 数出每个递归子问题的数量和规模；
4. 计算当前层非递归工作 f(n)；
5. 判断子问题是否重叠、是否随机；
6. 选择展开、树、主定理或其他方法；
7. 用归纳或上下界检查结论；
8. 单独分析空间、栈深度和实际成本模型。

完成检查

为二分查找、归并排序、快速排序和一个树遍历分别：

1. 写出最好、平均或最坏情况所需假设；
2. 建立时间递推；
3. 判断主定理是否适用；
4. 求渐近界；
5. 写出递归深度和额外空间；
6. 指出实现中哪项操作若改变，会使递推失效。

参考资料

• MIT 6.046: Recurrences
• MIT OpenCourseWare：Introduction to Algorithms