关系式

假设有递归关系式 $T(n)=a\cdot T\left(\frac{n}{b}\right)+f(n)$，其中 $n$ 为问题规模，$a$ 为递推的子问题的数量，$\frac{n}{b}$ 为每个子问题的规模（假设基本一样），$f(n)$ 为额外需要进行的计算工作。

关系式中，$a\ge 1$，$b>1$，$f(n)$ 为函数，$T(n)$ 为非负整数。

主定理

记 $c_{\text{crit}}=\log_b a$，则有如下分类讨论：

1. 如果存在常数 $c<c_{\text{crit}}$，满足 $f(n)=\mathcal O(n^c)$，那么 $T(n)=\Theta(n^{c_{\text{crit}}})$
2. 如果存在常数 $k\ge 0$，满足 $f(n)=\Theta(n^{c_{\text{crit}}}\log^k n)$，那么 $T(n)=\Theta(n^{c_{\text{crit}}}\log^{k+1} n)$
3. 如果存在常数 $c>c_{\text{crit}}$，满足 $f(n)=\Omega(n^c)$，那么 $T(n)=\Theta(f(n))$

注意

情形 $3$ 的条件：存在常数 $k<1$ 以及充分大的 $n$，满足 $a\cdot f\left(\frac{n}{b}\right)\le k\cdot f(n)$