time-complexity - 如何使用主方法解决 T(n) = 9T(n/3) + 2n^2 + n/3 的时间复杂度？

Question

我无法弄清楚 f(n) 是什么？是 n^2 还是 2n^2 + n/3 ？如何解决这些问题？提前致谢

Answer 1

回忆主定理如下：给定递归方程

T(n) = b*T(n/c) + f(n),

它适用于E = log(b)/log(c)：

1. if f(n)is in O(N^(E - eps))for some eps > 0, then T(n)is in Theta(n^E);
2. 如果f(n)在Theta(N^E)，则T(n)在Theta(N^E * log(n))；
3. 如果f(n)在Omega(N^(E + eps))一些eps > 0和另外b*f(n/c) <= d*f(n)一些d < 1并且n足够大，则T(n)在Theta(f(n)).

否则，主定理对您没有帮助。（你可以从每一本关于算法的基础教科书中得到这个定义，或者使用谷歌。）

根据您的定义，我们有b = 9andc = 3和f(n) = 2*n^2 + n/3。因此很容易证明案例 2 成立E = 2并且f(n)在 中Theta(n^2)。因此，T(n)在Theta(n^2 * log(n)).