形式陈述

设 $a\ge 1$、$b>1$，$f(n)$ 渐近非负，并考虑

$$T(n)=aT(n/b)+f(n),T(1)=\mathrm{\Theta }(1),$$

先在 $n=b^k$ 上陈述；取整版本在通常正则假设下相同。令 $d={\log }_{b}a$。经典主定理给出：

1. 若存在 $\epsilon >0$ 使 $f(n)=O(n^{d-\epsilon })$，则 $T(n)=\mathrm{\Theta }(n^d)$；
2. 若 $f(n)=\mathrm{\Theta }(n^d{\log }^{k}n)$，其中常数 $k\ge 0$，则 $T(n)=\mathrm{\Theta }(n^d{\log }^{k+1}n)$；
3. 若存在 $\epsilon >0$ 使 $f(n)=\mathrm{\Omega }(n^{d+\epsilon })$，并且对某个 $c<1$ 及充分大的 $n$ 有 $af(n/b)\le cf(n)$，则 $T(n)=\mathrm{\Theta }(f(n))$。

不满足这些多项式间隔或正则条件时，不能仅凭“看起来更大/更小”套用本定理。

直觉

递归树的总代价由叶子数量、各层均摊成本或根部合并工作中的最大者主导。

例子与边界

归并排序 $T(n)=2T(n/2)+\mathrm{\Theta }(n)$ 得到 $\mathrm{\Theta }(n\log n)$。$T(n)=T(n/2)+T(n/3)+n$ 不符合等规模子问题形式，不能直接套用主定理。

推论与应用

主定理快速分析排序、矩阵算法和树递归；不适用时可用递归树、代入法或 Akra–Bazzi 定理。

参考资料

• Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., §4.5.
• Manuel Akra and Louay Bazzi, “On the Solution of Linear Recurrence Equations,” 1998.