不使用主定理求解归并排序递推式T(n) = 2T(n/2) + n/2的复杂度

你的推导过程存在一个系数处理的小错误，我们重新一步步展开推导即可得到正确结果：

1. 初始递推式：T(n) = 2T(n/2) + n/2，边界条件设为T(1) = C（C为常数，代表单个元素的排序耗时）
2. 第一次展开替换T(n/2)：
   T(n) = 2 * [2T(n/4) + (n/2)/2] + n/2 = 2^2 T(n/4) + n/2 + n/2
3. 第二次展开替换T(n/4)：
   T(n) = 2^2 * [2T(n/8) + (n/4)/2] + 2*(n/2) = 2^3 T(n/8) + 3*(n/2)
4. 推广到第k次展开的通用形式：
   T(n) = 2^k * T(n/2^k) + k*(n/2)

当子问题规模降到1时，满足n/2^k = 1，即2^k = n，可得展开层数k = log_2 n。
将k代入通用形式：
T(n) = 2^{log_2 n} * T(1) + log_2 n * (n/2) = C*n + (n log_2 n)/2

接下来推导复杂度上下界：

• 下界：当n足够大时，(n log_2 n)/2 ≤ T(n)，因此T(n) = Ω(n log n)
• 上界：当n足够大时，T(n) = (n log n)/2 + C n ≤ (n log n)/2 + n log n = 3n log n /2，因此T(n) = O(n log n)

上下界结合即可得到T(n) = Θ(n log n)。

之前推导的问题说明 #

你之前展开时没有正确累加每一层所有子问题的非递归项总和：每一层有2^m个规模为n/2^m的子问题，每个子问题的非递归开销为(n/2^m)/2，因此每一层的总非递归开销为2^m * (n/(2^{m+1})) = n/2，一共有log_2 n层，总非递归开销为(n/2)*log_2 n，而非你之前写的等比数列求和。

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