求证时间复杂度求和结果及求解递推关系式T(n)=2T(n/2)+log(n)

一、验证求和式的时间复杂度 #

你的判断是正确的，该求和式的时间复杂度为O(nlogn)，推导过程如下：

假设n是2的幂（复杂度分析中仅需考虑该情况，不影响最终量级结论），令n=2^m，则求和式可展开为：
sum_{k=0}^m 2^k · log(n/2^k)
（最后一项k=m时，log(n/2^m)=log1=0，对总和无贡献）

将log(n/2^k)拆分为logn - k·log2（以2为底时log2=1，不影响量级），求和式拆分为两部分：

1. logn · sum_{k=0}^m 2^k：等比数列求和得logn·(2^{m+1}-1)=logn·(2n-1)，量级为O(nlogn)
2. sum_{k=0}^m k·2^k：利用等比数列求和公式，结果为(m-1)·2^{m+1}+2=(log₂n -1)·2n +2，量级为O(nlogn)

两部分相减后，总和的主导项为nlogn，因此整个求和式的时间复杂度是O(nlogn)。

二、递推关系式T(n)=2T(n/2)+log(n)的求解 #

我们采用递归展开法求解（假设n为2的幂，n=2^m，T(1)=1）：

1. 展开递推式：
   T(2^m) = 2T(2^{m-1}) + log(2^m) = 2T(2^{m-1}) + m
   继续展开到基例：
   T(2^m) = 2^m·T(1) + sum_{k=0}^{m-1}2^k·(m - k)

2. 代入基例T(1)=1：
   T(2^m) = 2^m + sum_{k=0}^{m-1}2^k·(m - k)

3. 计算求和项：
   令t = m - k，求和项转化为2^m·sum_{t=1}^m t·(1/2)^t。已知无穷级数sum_{t=1}^∞ t·(1/2)^t = 2，因此有限项求和结果小于2，即求和项的量级为O(n)（因为2^m=n）。

4. 最终结果：
   T(2^m) = n + O(n) = O(n)

进一步验证可知，T(n)的下界为Ω(n)，因此递推式的复杂度解为T(n)=Θ(n)。若需精确表达式，推导可得：
T(n) = 3n - log₂n - 2
（代入递推式和基例T(1)=1可验证成立）

内容的提问来源于stack exchange，提问作者Tanish Agarwal