解决T（n）= 2T（n / 2）+ nlogn的运行时间

Question

我试图以某种方式解决这个问题，我已经知道它的复杂性是BigTheta（nloglogn），但如果我执行以下操作，我不会得到相同的答案：

让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，我得到BigTheta((logn)^2)，这是不一样的。

Answer 1

你跟着我的朋友正确的方法。但是有一点点错误。

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)

Answer 2

好的，所以这里的错误就在这一行：

现在，如果我让S(m)=T(2^m)/2^m我将有S(m)=S(m-1)+m。

事实上，如果你让S(m)=T(2^m)/2^m，那么你将有S(m)=2S(m-1)+m，因为2^(m-1)的划分。

有了这个修正，我们有：

S(m) = 2S(m - 1) + m
     = 2S(2S(m - 2) + m) + m
     = 4S(m - 2) + (m − 1) + m
     = 4S(2S(m - 3) + (m - 2)) + (m − 1) + m
     = 8S(m - 3) + (m - 2) + (m - 1) + m

这给了我们一般形式：

S(m) = 2^m S(0) + m(m+1)/2

重新插入，我们有：

T(2^m) = 2^m T(0) + m(m+1) 2^(m-1)

然后我们可以重新插入n：

T(n) = nT(1) + n/2 (logn)(1 + logn) = O(n(logn)^2)