master theorem

分治的骨架与复杂度

分治算法的形状高度雷同：切开、递归、拼回。真正区分它们的是代价，而代价可以完全由一条递归式刻画。本页把这条递归式展成一棵 recursion tree，从树的形状读出 master theorem 的三种情形，再走到它管不到的地方。

1 · 递归式里的参数

一个分治算法只做三件事：divide 把规模 $n$ 的问题切成若干个同类的小问题，conquer 递归解决它们，combine 把子答案拼回一个答案。除去递归本身，divide 与 combine 的开销可以直接数出来，于是整个算法的代价满足

T(n) = a \cdot T(n/b) + f(n)

三个参数各管一段： $a$ 是切出多少个子问题， $b$ 是每个子问题的规模缩小多少倍， $f(n)$ 是 divide 与 combine 两端合起来的非递归代价。

$a$ 与 $b$ 彼此独立，这一点常被误当成同一个数。binary search 把区间切成两半却只递归一半， $a = 1$ 、 $b = 2$ ；merge sort 两半都要递归， $a = b = 2$ ；Karatsuba 同样切成两半，却做了三次半长乘法， $a = 3$ 、 $b = 2$ 。 $a$ 数的是递归调用的条数， $b$ 数的是规模的缩小倍率，两者没有任何理由相等。

注 · 递归式写成 $T(n/b)$ 是把 $n$ 当作 $b$ 的幂在算。真实实现里切出来的是 $\lfloor n/b \rfloor$ 与 $\lceil n/b \rceil$ ，两者相差至多 1，逐层累积的偏差不改变渐近阶。本页的展开一律取 $n = b^L$ ，好让每一层的规模都是整数，逐层代价表里不出现与结论无关的 $\pm 1$ 抖动。

警示 · 递归式能刻画代价，前提是子问题互不重叠。 $T(n) = 2T(n/2) + \Theta(n)$ 之所以等于 $\Theta(n \log n)$ ，靠的是两个半区各算各的、互不复用。一旦子问题之间有重合（Fibonacci 的两个递归分支共享大量子问题），同一条递归式仍然成立，但它算出的是重复计算之后的总量，指数级的那种。这条分界就是分治与动态规划的分界：不重叠则分治，重叠则记忆化。

2 · recursion tree 的逐层展开

把递归式一层层摊开成一棵树：树根是规模 $n$ 的那个问题，它自己付出 $f(n)$ ；它的 $a$ 个孩子各是规模 $n/b$ 的问题，各付 $f(n/b)$ 。递推下去，第 $i$ 层有 $a^i$ 个子问题，每个规模 $n/b^i$ ，该层的总代价是

a^i \cdot f(n/b^i)

树高由规模递减到基例决定： $n/b^L = 1$ 给出 $L = \log_b n$ 。最底层的叶子数是 $a^L = a^{\log_b n} = n^{\log_b a}$ ，每个叶子只付一份基例常数，整个叶子层的代价就是 $n^{\log_b a}$ 。

指数 $\log_b a$ 是后面全部结论的分水岭。它只由 $a$ 与 $b$ 决定，与 $f$ 无关：它衡量的是「光是把问题切到底、什么都不做」要付多少。

取 $f(n) = n^c$ 代进去，第 $i$ 层的代价是

a^i \left( \frac{n}{b^i} \right)^c = n^c \left( \frac{a}{b^c} \right)^i

逐层代价成了一个首项 $f(n)$ 、公比 $r = a/b^c$ 的等比数列。总代价是这条数列前 $L$ 项的和，加上叶子层的 $n^{\log_b a}$ 。公比 $r$ 与 1 的大小关系决定这个和的形状，也就决定了整个算法的复杂度。

图 2-1 · 递归树的逐层展开。可换预设或直接调

a

、

b

、

c

，观察层代价条从递减变为持平再变为递增，以及右侧的判定随之改写。

警示 · 叶子层付的是基例常数，不是 $f(1)$ 。实现 expand 时若图省事、把叶子层也代进 $f$ ， $f(n) = n \log n$ 这一族当场出错： $\log_2 1 = 0$ 让 $f(1) = 0$ ，叶子层的代价整个消失，而情形一的答案恰好全压在这一层上。recurrence.test.ts 里那条「叶子层按基例常数计」的断言就是为这个坑留的。

3 · master theorem 的分水岭

比较 $f(n)$ 与 $n^{\log_b a}$ ，就得到三种情形。

定理 3.1 设 $a \ge 1$ 、 $b > 1$ 、 $f$ 非负， $T(n) = aT(n/b) + f(n)$ 。

情形一：若存在 $\epsilon > 0$ 使 $f(n) = O(n^{\log_b a - \epsilon})$ ，则 $T(n) = \Theta(n^{\log_b a})$ 。

情形二：若 $f(n) = \Theta(n^{\log_b a})$ ，则 $T(n) = \Theta(n^{\log_b a} \log n)$ 。

情形三：若存在 $\epsilon > 0$ 使 $f(n) = \Omega(n^{\log_b a + \epsilon})$ ，且存在 $\kappa < 1$ 使 $a f(n/b) \le \kappa f(n)$ 对充分大的 $n$ 成立，则 $T(n) = \Theta(f(n))$ 。

三种情形问的是同一个问题：代价压在树根、均摊各层，还是压在叶子。 $f(n) = n^c$ 时它就是公比 $r = a/b^c$ 与 1 的大小关系：

$r > 1$ （即 $c < \log_b a$ ）：逐层代价几何递增，末项占绝对多数，总和与叶子层同阶，得情形一的 $\Theta(n^{\log_b a})$ 。
$r = 1$ （即 $c = \log_b a$ ）：每层代价相等，谁也不占优，得情形二。
$r < 1$ （即 $c > \log_b a$ ）：逐层代价几何递减，首项占绝对多数，总和与 $f(n)$ 同阶，得情形三的 $\Theta(f(n))$ 。

情形三多出的正则性条件 $a f(n/b) \le \kappa f(n)$ 正是「几何递减」这句话的严格版本：它要求下一层的总代价确实比本层小一个固定比例，而不只是 $f$ 本身增长得快。 $f$ 若在增长中带振荡，比较大小成立而递减不成立，情形三就不适用。

3.1 · 情形二的 log 因子

情形二的 $\log n$ 常被读成「 $f$ 里带了个 $\log$ 」，事实相反： $f(n) = \Theta(n^{\log_b a})$ 里没有任何 $\log$ 。这个因子来自层数。 $r = 1$ 时每一层的代价都等于 $n^{\log_b a}$ ，而树共有 $\log_b n + 1$ 层，求和就是拿层代价乘上层数。merge sort 的 $n \log n$ 里， $n$ 是每层要扫一遍的元素总数， $\log n$ 是扫了多少遍。

对数的底数无关紧要： $\log_b n$ 与 $\log_2 n$ 只差常数倍，写进 $\Theta$ 就被吸收掉了。

3.2 · 几条真实的递归式

算法	$a$	$b$	$f(n)$	$\log_b a$	情形	$T(n)$
binary search	1	2	$\Theta(1)$	0	二	$\Theta(\log n)$
merge sort	2	2	$\Theta(n)$	1	二	$\Theta(n \log n)$
平面最近点对	2	2	$\Theta(n)$	1	二	$\Theta(n \log n)$
Karatsuba	3	2	$\Theta(n)$	1.585	一	$\Theta(n^{1.585})$
Strassen	7	2	$\Theta(n^2)$	2.807	一	$\Theta(n^{2.807})$
分块矩阵乘法	8	2	$\Theta(n^2)$	3	一	$\Theta(n^3)$
合并占优的分治	2	2	$\Theta(n^2)$	1	三	$\Theta(n^2)$

注 · 表里最后一行的 $\Theta(n^2)$ 与倒数第二行的 $\Theta(n^3)$ 都由 $f$ 决定过一次，很容易串。写 recurrence.test.ts 时，把 $T(n) = 8T(n/2) + \Theta(n^2)$ 判成了情形二、答案写作 $n^3 \log n$ ，跑测试当场被判错： $\log_2 8 = 3$ 比 $c = 2$ 大，它属于情形一，答案是 $n^3$ ，那个 $\log$ 因子并不存在。误判的来路是拿 $f$ 与「合并一次要多少」比，而定理要求拿它与 $n^{\log_b a}$ 比。

4 · master theorem 够不到的地方

定理的三条前提都要求 $f(n)$ 与 $n^{\log_b a}$ 之间差着一个 $n^{\epsilon}$ 那么大的因子，或者干脆同阶。两者只差一个 $\log$ 的情形，三条一条都不满足。

最短的例子是 $T(n) = 2T(n/2) + n \log n$ 。此时 $\log_b a = 1$ ， $f(n) = n \log n$ 比 $n$ 大，但对任何 $\epsilon > 0$ ， $n \log n$ 都不是 $\Omega(n^{1 + \epsilon})$ ，情形三不适用； $f$ 也不是 $\Theta(n)$ ，情形二不适用；更谈不上比 $n$ 多项式地小。

递归树照样能加。第 $i$ 层有 $2^i$ 个规模 $n/2^i$ 的子问题，该层代价是

2^i \cdot \frac{n}{2^i} \log \frac{n}{2^i} = n(\log n - i)

这是一个公差为 $-n$ 的等差数列， $L = \log_2 n$ 层求和得 $n \cdot L(L+1)/2$ ，再加叶子层的 $n$ 。答案是 $\Theta(n \log^2 n)$ ，比 $n \log n$ 高一整个 $\log$ 。

expand 在 $n = 16, 64, 256, 1024$ 上给出的树和是 176、1408、9472、57344，与 $n \log n$ 的比值依次为 2.75、3.67、4.63、5.60。比值随 $n$ 稳定增长而不收敛到常数，这本身就足以否掉 $n \log n$ 这个答案。

图 4-1 · 等差型层代价的逐层累加。左侧是

n \log n

合并的层代价条，右侧同步给出树和与两个候选答案的比值。可调规模观察比值是否收敛。

注 · Akra–Bazzi 方法补上了这条缝，代价是换一套工具。它允许每个子问题有各自的一对系数，先解 $\sum_i a_i b_i^{-p} = 1$ 定出指数 $p$ ，再算 $T(n) = \Theta(n^p (1 + \int_1^n f(u) u^{-p-1} \, \mathrm{d}u))$ 。对本页这一族 $f(n) = n^c \log^k n$ ， $p$ 就是 $\log_b a$ ； $c = p$ 时积分给出 $\log^{k+1} n / (k+1)$ ， $T(n) = \Theta(n^p \log^{k+1} n)$ ，与逐层相加的结果一致。akraBazzi 与 masterCase 在测试里逐条比对过，包括 $k = 0$ 的三种情形。

分治的复杂度分析里，真正需要动脑的部分往往不在解递归式，而在写出递归式之前： $f(n)$ 到底是多少。计数 · 取幂 · 大整数乘法一页里，Karatsuba 的全部巧妙之处就是把 $a$ 从 4 压到 3，而 $f$ 一动不动。

5 · 参考文献

Bentley, J. L., Haken, D., & Saxe, J. B. (1980). A general method for solving divide-and-conquer recurrences. ACM SIGACT News, 12(3), 36–44.
Akra, M., & Bazzi, L. (1998). On the solution of linear recurrence equations. Computational Optimization and Applications, 10(2), 195–210.
Leighton, F. T. (1996). Notes on better master theorems for divide-and-conquer recurrences. Manuscript, MIT.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.