Creator's World

假设有递推关系式 $T(n)=aT(\frac{n}{b})+f(n)$，求它的时间复杂度。

设 $d=\log_ba$，则存在以下关系：

1. 当 $f(n)=O(n^c)$，且 $c<d$ 时

$T(n)=\Theta(n^d)$

2. 若存在一个 $k>-1$，使得

$f(n)=\Theta(n^d\log^kn)$

$\quad$ 那么

$T(n)=\Theta(n^d\log^{k+1}n)$

$\quad$ $k=-1$ 时，

$T(n)=n^d\log\log n$

$\quad$ $k<-1$ 时，

$T(n)=n^d$

3. 当 $f(n)=\Omega(n^c)$ 且 $c>d$ 时

$T(n)=\Theta(f(n))$