初赛复习：主定理

对于形如：
$$T(n)=aT(\frac{n}{b})+f(n)$$
那么，我们可以用下述三个公式来刻画\(T(n)\)的渐近上下界。
$$f(n)=\Theta(n^{log_ba-\epsilon}),\epsilon >0\Rightarrow T(n)=\Theta(n^{log_ba})$$
$$f(n)=\Theta(n^{log_ba+\epsilon}),\epsilon >0\Rightarrow T(n)=\Theta(f(n))$$
$$f(n)=\Theta(n^{log_ba})\Rightarrow T(n)=\Theta(n^{log_ba}logn)$$
换而言之，就是，比较\(f(n)\)和\(\Theta(n^{log_ba})\)的级别。如果两者同级，就乘上一个log，否则就取较大的。