递归程序每层写着两次调用，不意味着总成本就是“层数乘以 n”。子问题有多大、每层共有多少节点、局部工作是否包含复制，都要从实际代码得到。第 01 篇的树聚合已经给出一个反例：左右子树可以很不均衡，遍历时间仍为线性，栈深却可能为线性。

本篇只讨论确定性的最坏成本与比较模型下界。输入规模 n 为元素数，单次比较和引用移动视为单位成本；目标是推导随 n 增长的工作量，不估算墙上时间。下文递推式是被声明的成本模型，不能自动代替任意同名算法的真实实现。

均衡递归的每层账目

对二路均衡归并，设 n 为 2 的幂，边界 $T(1)=c_0$ ，每个内部节点的拆分和合并总工作为 cn，c 为正的固定常数：

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

第 j 层有 $2^j$ 个子问题，每个大小为 $n/2^j$ ，所以该层局部工作是 cn。内部层共有 $\log_2 n$ 层，叶子 n 个，总成本为 $cn\log_2 n+c_0n$ ，因此是 Θ(n log n)。对任意 n，取整会让层末不整齐，但不改变渐近阶。将规模上包到下一个 2 的幂可得上界，再按实际合并层数给出下界。

递归树把“猜测”变成了求和对象。要形成证明，还须交代层数、每层成本和叶子成本。只画一棵 n=8 的树能帮助发现规律，不能证明所有 n 都遵循它。

代入法提供另一个检查：假设子问题满足 $T(n/2)\le A(n/2)\log_2(n/2)+B(n/2)$ ，代回得到 $T(n)\le An\log_2n+Bn+(c-A)n$ 。选择 $A\ge c$ ，并让 B 覆盖边界，即得到上界。若要声称 Θ，还需独立下界；不能把一次 O 上界代入包装成双向界。

偏斜递归改变求和

若一次划分后只减去一个元素，而局部工作仍为 cn：

T(n)=T(n-1)+cn,\quad T(1)=c_0.

展开得到 $c(2+3+\cdots+n)+c_0=\Theta(n^2)$ 。递归深度为 n-1，活动栈帧数量也是线性级。若每层还复制剩余数组，峰值空间不能只算栈帧个数，要检查这些数组是否同时存活。

快速排序的划分大小来自输入和枢轴规则。最坏情况下可出现上面的偏斜形状；随机选择枢轴的期望分析需要对随机划分大小求和，不能写成 2T(n/2)+cn 就宣布证明了期望界。均衡递推最多描述恰好均衡的路径。第 32 篇再给随机选择的分析条件。

还有一种线性递归：第 01 篇聚合树， $T(n)=T(n_L)+T(n_R)+c$ ，其中 $n_L+n_R=n-1$ 。对节点数归纳，每个节点收费一次即得 Θ(n)，无须假定左右均衡。局部费用是常数而非 cn，这一点足以改变总和。

主方法的适用范围

主方法压缩的是一类固定比例递归的求和。采用如下版本： $a\ge1,b>1$ 为常数， $T(n)=aT(n/b)+f(n)$ ，f 渐近为正，基本问题成本为正常数，整数规模按一致方式取整。令 $d=\log_b a$ 。MIT 讲义给出的三种情况如下。MIT 6.046 Recitation 2

条件	结论
存在固定 ε>0，使 $f(n)=O(n^{d-\varepsilon})$	$T(n)=\Theta(n^d)$
$f(n)=\Theta(n^d\log^k n)$ ，固定 k≥0	$T(n)=\Theta(n^d\log^{k+1}n)$
存在固定 ε>0，使 $f(n)=\Omega(n^{d+\varepsilon})$ ，并且对充分大的 n 有 $af(n/b)\le cf(n)$ ，固定 c<1	$T(n)=\Theta(f(n))$

第三行的正则条件限制 f 在不同尺度间的变化，使根层占主导的直觉能成立。仅比较 f 与 $n^d$ 在少数 n 上的大小不够。a、b 也不能随 n 随意变化，T(n-1) 不属于这个固定比例形式。

对于 $2T(n/2)+n/\log n$ ，f 比 n 小，但不存在固定 ε>0 让它成为 $O(n^{1-\varepsilon})$ ，所以不落入第一行。它也不满足这里第二行要求的 k≥0。这是“定理不给答案”的例子，不是“递推没有答案”。Cornell 的递推讲义用这一形式说明适用范围的间隙。Cornell Recitation 20

可以直接求和。设 n= $2^h$ ，在规模至少为 2 的层，第 j 层工作为 $n/(h-j)$ 。总内部工作为 $n\sum_{t=1}^{h}1/t=\Theta(n\log h)$ ，叶子另加 Θ(n)，最终为 Θ(n log log n)。调和级数的对数界可通过把 $1/t$ 与积分比较得到；n=1 的边界单独定义，避免除以零。

下界是在限制哪一种算法

比较排序的输入取 n 个互异键。算法只能通过两键比较获得相对次序；固定算法的分支可以画成二叉决策树，每个叶子对应一种最终排列。允许输入有 n! 种相对次序，正确排序必须区分它们，因此至少需要 n! 个叶子。

高度为 h 的二叉树最多有 $2^h$ 个叶子，于是最坏比较次数满足：

h\ge\lceil\log_2(n!)\rceil.

不必先引用 Stirling 公式。乘积 n! 的最后约 n/2 个因子都至少为 n/2，所以 $\log_2(n!)\ge(n/2)\log_2(n/2)=\Omega(n\log n)$ 。这是对任意确定性比较排序的最坏输入下界。MIT 的排序讲义采用相同的决策树框架。MIT 6.006 Lecture 5

下界没有禁止计数排序。若键来自整数范围 [0,U)，可以直接用键寻址计数数组，再按整数次序输出；时间为 O(n+U)，额外计数空间 O(U)，需要可寻址的整数宇宙及单位成本索引操作。这里一次操作获得的信息不再局限于两键比较的一比特分支。若 U 远大于 n，空间和初始化也可能不可接受。

随机算法的平均决策树深度、重复键的输入数量、允许错误的模型，需要另外论证。不能把当前确定性互异键证明不加解释地推广到所有模型。

手算校验与实现边界

这一篇无需新增排序实现。可检查结果是前述递推的精确值：将局部常数设为 1，边界设为 1，均衡递推在 n=1、2、4、8 时依次为 1、4、12、32；偏斜递推为 $n(n+1)/2$ ，相应得到 1、3、10、36。两组数来自公式代入，不是实测耗时。

同一 n=8 下两者已经不同，但四个数字不能确认渐近阶。真正支撑 Θ 结论的是对全部合法规模的求和。后续做操作计数时应让计数器对应这里的“局部工作”，不要把解释器指令、比较次数和墙上时间混成同一单位。

本篇模型检查卡列出各递推的边界与证明方式。分析新递归时，先记录每个真实子问题规模，再累加局部成本；只有形状匹配，才使用主方法。

对 $T(n)=3T(n/2)+n$ ，n 为 2 的幂，写出每层总工作并推导 Θ 界。再将局部工作换成 $n^2$ ，检查第三种情况的正则条件。
有人将第 01 篇树聚合的递推写成 $2T(n/2)+n$ 。用一棵链指出“子问题规模”和“局部工作”两处不符，写出正确的节点收费论证，并解释时间线性为何不能推出栈空间对数。

参考资料

MIT 6.046 Recitation 2，第 2 页主方法，本文使用 k≥0 的扩展第二种情况。
Cornell CS3110 Recitation 20，递推与定理适用范围。
MIT 6.006 Lecture 5，比较排序决策树下界。