algorithm - 求解T(n)= 2T(n/2)+ nlogn的运行时间

我试图以某种方式解决这个问题，我已经知道它的复杂性是Bigtheta（nLogGLGN），但是如果我做了以下的事情，我就不会得到同样的答案：
设m=logn，然后n=2^m得到T(2^m)=2T(2^(m-1))+(2^m)*m，乘以1/(2^m)得到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是不一样的。

最佳答案

你走对了，我的朋友不过有一个小错误。

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)