我试图以某种方式解决这个问题，我已经知道它的复杂性是 BigTheta(nloglogn) ，但如果我执行以下操作，我不会得到相同的答案：
let m = logn
then n = 2^m
we get T(2^m) = 2T(2^(m-1))+(2^m)*m
multiply by 1/(2^m)
we get T(2^m)/2^m = 2T(2^(m-1))/2^m + m
= T(2^(m-1))/(2^(m-1)) + m
现在，如果我让S(m)=T(2^m)/2^m我将有S(m)=S(m-1)+m。
现在我S(m)=S(m-1)+m用回代法解决。
S(m) = S(m-1)+m=S(m-2)+(m-1)+m = S(m-3)+(m-2)+(m-1)+m = S(m-4)+(m-3)+(m-2)+(m-1)+m=... = S(m-k)+(m-k+1)+..+(m-3)+(m-2)+(m-1)+m = ... = S(1)+2+...+m = m(m-1)/2 = BigTheta(m^2)
插回去m=logn，我得到的BigTheta((logn)^2)是不一样的。
你遵循了正确的方法，我的朋友。不过有一个小错误。
S(m) = S(m-1) + m
这是正确的，我们得到S(m) = BigTheta(m^2).
现在S(m) = T(2^m)/(2^m) = BigTheta(m^2)。这意味着T(2^m) = T(n) = (2^m) * BigTheta(m^2).
放回我们得到的值 T(n) = n*BigTheta(lognlogn) = BigTheta(n*lognlogn)
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句