初赛复习:主定理

对于形如:
$$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,否则就取较大的。

发表评论

电子邮件地址不会被公开。