algorithm - 求算法的运行成本

Question

我无法解决以下复发

T(n) = 3T(n/5) + lg^2 n

我的工作：应用主定理

 a=3 b=5

 n^log5^3n= n^log^0.65

这导致n^0=1这与 l 无法比较og^2n

我也尝试使用递归树，但它太复杂了。请帮忙。

Answer 1

T(n) = a*T(n/b) + f(n)
这里，

a = 3
b = 5
f(n) = (lg(n))^2

现在，根据大师定理的第一个案例，

如果对于某个常数 e > 0，f(n) = O(n^logb(a−e))，则 T(n) = Θ(n^logb(a))。

让我们取e = 3-sqrt(5)
因此，n^logb(a−e) = n^log5(3-(3-sqrt(5))) = n^log5(sqrt(5)) = n^ 0.5 = sqrt(n)。

所以，我们现在必须比较(lg(n))^2和sqrt(n)。
如果我们绘制这两个函数的图，我们可以清楚地观察到(lg(n))^2 = O(sqrt(n))。

由于 f(n) = O(n^logb(a−e)) 对于 b = 5，a = 3 和 e = 3-sqrt(5)，
T(n) = Θ(n^logb(a))

=> T(n) = Θ(n^0.68)