我正在尝试以某种方式解决这个问题，我已经知道它的复杂性是 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)，这是不一样的。
最佳答案
我的 friend ，你遵循了正确的方法。不过有一个小错误。
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)
关于algorithm - 求解运行时间T(n)=2T(n/2)+nlogn，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48050136/