主方法

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

下面对 f 函数的重要性进行讨论

---

如果存在某个常数 $ϵ>0$ 有

$$f(n)=O(n^{{\log }_{b}a-ϵ})$$

则

$$T(n)=\Theta (n^{{\log }_{b}a})$$

---

若 $f(n)=\Theta (n^{{\log }_{b}a})$

$$T(n)=\Theta (n^{{\log }_{b}a}lgn)$$

---

若某个常数 $ϵ>0$ 有

$$f(n)=\Omega (n^{{\log }_{b}a+ϵ})$$

且对常数 $c<1$，与所有足够大的 n 有

$$af\left(\frac{n}{b}\right)\le cf(n)$$

则

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