主定理速成

发表于 2025-09-20

对于时间复杂度形如

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

的递归过程，有

$f(n)=O(n^c),c<\log_ba$ ，则 $T(n)=\Theta(n^{\log_b a})$ ，此时递归树的调用复杂度更大；
$f(n)=\Theta(n^{\log_ba}\log^kn),k\ge 0$ $f (n) = Θ (n^{l o g_{b} a} lo g^{k} n), k \geq 0$ ，则 $T(n)=\Theta(n^{\log_ba}\log^{k+1}n)$ $T (n) = Θ (n^{l o g_{b} a} lo g^{k + 1} n)$ ；更一般地，对于所有 $k$ $k$ ，
- 若 $k>-1$ ，则 $T(n)=\Theta(n^{\log_ba}\log^{k+1}n)$ ；
- 若 $k=-1$ ，则 $T(n)=\Theta(n^{\log_ba}\log\log n)$ ；
- 若 $k<-1$ ，则 $T(n)=\Theta(n^{\log_ba})$ ；
$f(n)=\Omega(n^c),c>\log_ba$ ，且存在 $k<1$ 使得对于足够大的 $n$ ， $af(n/b)\le kf(n)$ ，则 $T(n)=\Theta(f(n))$ ，此时 $f$ 的调用复杂度更大。

简单的记忆方式：

若

T(n)=aT(n/b)+f(n)=aT(n/b)+O(n^c\log^kn)

则

T(n)= \begin{cases} O(n^{\log_ba}\log^{k+1}n)&c=\log_ba\\ O(\max\{n^{\log_ba},f(n)\})&\textrm{otherwise} \end{cases}

注意，上式牺牲了一定严谨性。