求解递归式T(n)=2T(n/2)+nlogn时推导结果与已知复杂度不符的疑问

首先给你吃个定心丸：你的推导过程完全正确，得到的 $T(n)=\Theta(n(\log n)^2)$ 才是递归式 $T(n)=2T(n/2)+n\log n$ 的正确时间复杂度。

你提到的 $\Theta(n\log\log n)$ 其实是另一个相似递归式的结果——$T(n)=2T(n/2)+\frac{n}{\log n}$，这两个递归式结构相近很容易搞混，我们来逐一拆解：

1. 你的推导为什么正确？ #

再梳理一遍你的步骤，确认逻辑无漏洞：

• 令 $m=\log n$（这里默认底数为2，时间复杂度分析中底数不影响最终结果），则 $n=2^m$，代入原递归式得：
  $$T(2^m)=2T(2{m-1}) + 2^m \cdot m$$
• 两边除以 $2^m$，定义 $S(m)=\frac{T(2^m)}{2m}$，得到简化后的递推关系：
  $$S(m)=S(m-1)+m$$
• 回代求解时，$S(m)=S(0)+1+2+\dots+m$，其中 $S(0)=T(1)=\Theta(1)$（初始条件为常数），因此 $S(m)=\Theta(m^2)$。
• 代回 $m=\log n$，得到 $T(n)=2^m \cdot S(m)=\Theta(n(\log n)^2)$，这个结果完全正确。

2. 为什么 $\Theta(n\log\log n)$ 属于另一个递归式？ #

对于递归式 $T(n)=2T(n/2)+\frac{n}{\log n}$，用递归树法推导更直观：

• 每层的代价和为 $\frac{n}{\log n} + \frac{n}{\log(n/2)} + \dots + \frac{n}{\log 2}$，总共包含 $\log n$ 层。
• 这个和可以改写为 $n \cdot \sum_{k=1}^{\log n} \frac{1}{k}$，而调和级数 $\sum_{k=1}^t \frac{1}{k}=\Theta(\log t)$，这里 $t=\log n$，因此总和为 $n \cdot \Theta(\log\log n)$，最终时间复杂度就是 $\Theta(n\log\log n)$。

3. 用主定理验证你的递归式 #

用主定理的情况2进一步确认：

• 对于 $T(n)=aT(n/b)+f(n)$，这里 $a=2, b=2$，所以 $n^{\log_b a}=n^1=n$。
• $f(n)=n\log n=\Theta(n(\log n)^1)$，符合主定理情况2中 $f(n)=\Theta(n^{\log_b a}(\log n)^k)$（$k=1\geq0$）的条件，因此 $T(n)=\Theta(n(\log n)^{k+1})=\Theta(n(\log n)^2)$，和你的推导完全一致。

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