求递归式T(n)=2T(n/2)+Logn的时间复杂度（递归树法困惑）

递归树结构拆解 #

• 第k层（从1开始计数）的节点数：2^(k-1)
• 第k层每个节点的工作量：log₂(n/(2^(k-1)))，因为每个子问题的规模是n/(2^(k-1))
• 树的高度：当子问题规模缩小到1时，n/(2^(k-1))=1，解得k=log₂n +1，因此总共有log₂n +1层——前log₂n层是非叶子节点（对应递归式中的log项），最后一层是叶子节点（对应T(1)）

非叶子节点的总工作量求和 #

把第k层的总工作量展开：

2^(k-1) * log₂(n/(2^(k-1))) = 2^(k-1) * (log₂n - (k-1))

这一步是利用对数性质：log₂(n/(2^(k-1))) = log₂n - log₂(2^(k-1)) = log₂n - (k-1)。

将所有非叶子节点的工作量求和（记为S），求和范围是k从1到log₂n：

S = Σ（k=1到m）[2^(k-1)*(log₂n - (k-1))]，其中m=log₂n

拆成两个独立求和项计算：

1. 第一项：log₂n * Σ（k=1到m）2^(k-1)

   • 等比数列求和：Σ（k=1到m）2^(k-1) = 2^m -1 = n -1（因为2^m =n）
   • 结果为：log₂n*(n-1)

2. 第二项：Σ（k=1到m）(k-1)*2^(k-1)

   • 令t=k-1，转化为Σ（t=0到m-1）t*2^t，用已知求和公式：Σ（t=0到n-1）t*2^t = (n-2)*2^n +2
   • 代入n=m，得：(m-2)*2^m +2 = (log₂n -2)*n +2

将两项相减得到S：

S = log₂n*(n-1) - [(log₂n -2)*n +2]
= n log₂n - log₂n -n log₂n +2n -2
= 2n - log₂n -2

显然S的时间量级是O(n)。

叶子节点的总工作量 #

最后一层有2^m =n个叶子节点，每个叶子节点对应T(1)，假设T(1)=O(1)，因此总工作量为n*O(1)=O(n)。

整体时间复杂度 #

将非叶子节点和叶子节点的工作量相加：T(n)=S + O(n)=O(n)+O(n)=O(n)。

你之前的错误原因 #

你没有展开对数拆分每一层的工作量，也没正确计算求和后的量级——实际上求和过程中log项会被抵消，最终主导项是n，而非logn。

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