本节接续 0.2 的循环计数与简单递归。默认你已能区分调用总数、调用深度和非递归工作；若还不熟悉，先用该节的七节点调用树手算一次。

分析递归算法时，先不要猜 O(n log n)。把当前调用之外的工作和子调用分开计费，复杂度通常可以写成：

$$T(n)=\sum T(n_i)+f(n),$$

其中 $n_i$ 是各子问题规模，$f(n)$ 是 Divide、Combine 和当前层其他工作的总和。

三个最重要的量

对规则分治

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

要辨认：

• $a$：真正递归求解的子问题数量；
• $b$：每个子问题相对原问题缩小的比例；
• $f(n)$：当前层不包含子调用的工作量。

WARN易错点 · 把“代码里出现几次函数名”当作 a

快速幂若把半幂保存到变量，只真正递归一次，$a=1$；若在乘法两边重复调用，才是 $a=2$。复杂度由真实执行次数决定，不由数学式里出现几次 $x^{n/2}$ 决定。

方法一：直接展开

若

$$T(n)=T(n/2)+c,$$

展开 $k$ 次得到 $T(n)=T(n/2^k)+kc$。当 $n/2^k=1$ 时，$k={\log }_{2}n$，所以 $T(n)=\mathrm{\Theta }(\log n)$。

快速幂和递归字符串逆向定位都属于这一类：每层只沿一条路径，当前层只做常数工作。

若某个算法保证每次只递归处理一半规模，但当前调用需要线性时间：

$$T(n)=T(n/2)+cn,$$

展开后得到 $cn+cn/2+cn/4+\cdots =O(n)$。

这能说明几何缩小的直觉，但不能直接把随机快速选择的期望子问题规模代入递推式，作为期望时间的证明；期望分析还需要处理划分规模的概率分布。

方法二：递归树逐层求和

归并排序满足：

$$T(n)=2T(n/2)+cn.$$

第 $i$ 层有 $2^i$ 个规模为 $n/2^i$ 的子问题，该层非递归工作总量是：

$$2^i\cdot c\frac{n}{2^i}=cn.$$

树高为 ${\log }_{2}n$，每层都是线性，总时间为 $\mathrm{\Theta }(n\log n)$。

IDEA直觉 · 递归树是工作账本

树高回答“有多少层”，每层结点数乘单结点工作回答“这一层多少钱”。最后把所有层相加。不要只看树高，也不要只看叶子数。

方法三：主定理

对于形如

$$T(n)=aT(n/b)+f(n),a\ge 1,b>1,$$

比较 $f(n)$ 与临界量 $n^{{\log }_{b}a}$：

情况	直观含义	常见结论
f(n) 多项式意义上更小	叶子/子问题增长占主导	$\mathrm{\Theta }(n^{{\log }_{b}a})$
f(n) 与临界量同阶并带对数因子	各层工作相近	多一个对数因子
f(n) 多项式意义上更大且满足正则条件	根部/合并工作占主导	$\mathrm{\Theta }(f(n))$

常用的简化版本：

• $2T(n/2)+O(1)=O(n)$；
• $2T(n/2)+O(n)=O(n\log n)$；
• $2T(n/2)+O(n^2)=O(n^2)$。

主定理的精确条件与紧界

假设基例为正的常数工作，a≥1、b>1 为常数，f(n) 最终非负，令 p=log_b a。标准三种情形为：

1. 存在常数 ε>0，使 f(n)=O(n^(p-ε))，则 T(n)=Θ(n^p)。
2. f(n)=Θ(n^p)，则 T(n)=Θ(n^p log n)。常见推广允许 f(n)=Θ(n^p log^k n)、常数 k≥0，得到 Θ(n^p log^(k+1) n)。
3. 存在常数 ε>0，使 f(n)=Ω(n^(p+ε))，并且存在常数 c<1，使充分大的 n 满足 a f(n/b)≤c f(n)，则 T(n)=Θ(f(n))。

第三种的正则条件不能漏掉；第一、三种要求多项式差距，不能把“略大一点”直接套进去。上面的简化例子只写 O 是上界；如果当前层工作分别为 Θ(1)、Θ(n)、Θ(n²)，则对应紧界为 Θ(n)、Θ(n log n)、Θ(n²)。

出处：Cormen、Leiserson、Rivest、Stein，Introduction to Algorithms，第 4 版，第 4 章。取整时应同时明确终止基例，避免规模降为零却没有定义。

使用边界

主定理不是所有递推式的万能公式。T(n)=T(n-1)+n、子问题大小不规则、相互重叠或 f(n) 不满足条件时，应使用展开、代换、递归树或更一般的工具。

不规则规模与最坏情况

快速选择或快速排序划分后规模依赖输入。理想情况近似两半，最坏情况可能是 0 与 n-1：

$$T(n)=T(n-1)+\mathrm{\Theta }(n)=\mathrm{\Theta }(n^2).$$

因此复杂度说明应区分最坏、期望与平均，而不能只写一个没有条件的 O(n)。

随机化枢轴降低连续极端划分的概率；三路划分改善大量重复值。它们改变的是划分分布，不改变算法的正确性合同。

输出规模是不可绕过的下界

12E03 · 南蛮图腾输出高度 $2^n$、宽度同阶的字符画，字符量为 $\mathrm{\Theta }(4^n)$。即使计算结构非常巧妙，完整打印也需要至少同阶时间。

12E10 · 地毯填补输出 $(4^k-1)/3$ 块骨牌，12E12 · 表达式所有结果的结果数量可能呈 Catalan 增长。对枚举或构造题，应写成“算法时间至少与输出量成正比”，而不是盲目追求多项式。

O(·)复杂度 · 时间、辅助空间与输出空间分开写

字符画若先在内存中构造，需要与输出量同阶的结果空间；若能流式输出，辅助空间可能更小。复杂度报告最好区分递归栈、临时缓冲区和最终输出本身。

空间复杂度：深度加辅助结构

常见组成包括：

来源	例子
调用栈	归并排序 O(log n)，线性链式递归 O(n)
合并缓冲区	归并排序共享 O(n) 数组
记忆化表	Function 的 O(21³) 状态
构造结果	四叉树结点、字符画、表达式结果集合

同时存在时应相加并取主导项。例如归并排序辅助数组 O(n) 大于调用栈 O(log n)，总辅助空间为 O(n)。

这里依据的是生存期。父调用若在进入子调用前申请并保留规模 n 的缓冲区，规模沿路径减半时，同时占用量为 n+n/2+…=Θ(n)；若每一层都保留一份原始长度 n 的副本，深度为 Θ(log n) 时就会占 Θ(n log n)。不能用“堆空间一律取 max”分析这两种程序。

完整例题：四叉树的朴素区域检查

若每个递归结点都扫描自己的整个区域判断是否统一，最坏情况下：

$$T(n)=4T(n/2)+\mathrm{\Theta }(n^2).$$

临界量 $n^{{\log }_{2}4}=n^2$ 与当前层扫描同阶，所以最坏时间为 $\mathrm{\Theta }(n^2\log n)$。若预处理二维前缀和，使统一性判断降为 $O(1)$，递推式变成 4T(n/2)+O(1)，最坏结点总数为 $O(n^2)$。

这说明优化入口常位于 $f(n)$，而不是递归调用本身。

ANTI反例 · 看到四个子问题就写 O(4^n)

这里的 n 是边长，每层边长减半，树高为 log n。叶子最多对应 n² 个单元格，因此结点量是 O(n²)，不是以边长为指数的 O(4^n)。若参数改为层数 k 且边长为 2^k，才可以写成 O(4^k)；变量含义必须明确。

自检

1. T(n)=3T(n/2)+O(n) 的临界量是什么？
2. 为什么递归深度不能直接当作时间复杂度？
3. 输出一百万个答案的算法能否做到 O(log n) 总时间？

参考答案

1. $n^{{\log }_{2}3}$。线性合并项多项式意义上更小，因此由子问题增长主导，结果为 $\mathrm{\Theta }(n^{{\log }_{2}3})$。
2. 每层可能有多个调用，每个调用还可能执行非递归工作；时间要累计整棵树，深度只描述最长路径。
3. 不能，至少需要 Ω(10^6) 次输出动作。可以做到的是低辅助空间或低“每个答案的额外开销”。

延伸阅读

不等规模递推的平方上界

EX拓展纠错 · 根节点本身已需平方工作

考虑非负工作量递推

$$T(n)=3T(\lfloor n/4\rfloor )+2T(\lfloor n/6\rfloor )+n^2.$$

为明确边界，取 0≤n<6 时 T(n)=1，n≥6 使用上式。正确结论为 Θ(n²)。两个子问题尺度不同，不能直接套单一缩小比例的主定理。

PROOF证明 · 不需要先求临界指数

根节点的非递归工作就是 n²，所以 T(n)≥n²。为证明上界，注意子问题规模平方之和满足

$$3(n/4{)}^2+2(n/6{)}^2=\frac{35}{144}{n}^2.$$

归纳假设较小的正整数规模满足 T(m)≤Cm²。对 n≥6，两个取整后的子规模均至少为 1，且取整不会增大平方项，因此

$$T(n)\le (\frac{35}{144}C+1)n^2\le C{n}^2$$

只需 C≥144/109，并让 C 足够大以覆盖基例 1,…,5。上下界合起来得到 T(n)=Θ(n²)。非负成本不可能小于根节点已经完成的工作。

用 Akra–Bazzi 检查原积分推导

对本例，临界指数满足 3·4^(-p)+2·6^(-p)=1。左边关于实数 p 严格递减，在 p=1 时为 13/12>1，在 p=2 时为 35/144<1，故唯一解满足 1<p<2，无须数值近似。

本例非递归项 g(u)=u² 是平滑多项式，子规模取整只带来有界扰动，可应用 Akra–Bazzi 公式。关键积分为

$${\int }_1^n\frac{u^2}{u^{p+1}}du=\frac{n^{2-p}-1}{2-p}=\mathrm{\Theta }(n^{2-p}).$$

因为 1-p 在 (-1,0) 内，积分随上限增长而发散；“指数为负”不等于积分收敛。代回得到 Θ(n^p(1+n^(2-p)))=Θ(n²)。

一般 Akra–Bazzi 方程 Σ aᵢbᵢ^p=1 在 aᵢ>0、0<bᵢ<1 下有唯一实数解，不保证为正。例如系数和为 1 时解为 0。完整定理还要求非递归项的增长条件和子规模扰动条件；本段只验证这个具体多项式实例，不把积分近似当作一般定理的证明。参见 Introduction to Algorithms 第 4 版第 4 章的 Akra–Bazzi 方法。

归纳没有闭合时先检查什么

ANTI反例 · 证明失败不等于猜想错误

取 T(1)=1、T(n)=2T(n/2)+1，先令 n 为 2 的幂。猜 T(n)=O(n)，若直接用 T(n)≤Cn 归纳，代入只得到 Cn+1，无法闭合。

但猜想是对的：加强为 T(n)≤Cn-1，归纳步得到 2(Cn/2-1)+1=Cn-1；C≥2 可覆盖基例。实际上展开得到 T(n)=2n-1。

检查顺序应是：基例是否覆盖，归纳假设是否足够强，取整是否处理，最后再寻找能否否定猜想的上下界证据。上例减去的是常数低阶项；Cn-dn 仍然只是一个线性项，不是降低次数的修补。

若递推改为 2T(n/2)+n，每一层非叶工作都是 n，有 log₂n 层，因此 T(n)=n log₂n+n（n 为 2 的幂）。这次 O(n) 猜想确实错误，证据是展开后的下界，不是“某一次归纳算不下去”。

后续材料

• OI Wiki：分治包含主定理与典型分治复杂度。
• Hello 算法：分治用递归树讨论分治效率。
• 本章下一节将复杂度、重叠性和输出需求合并成方法选择。