归并排序时间复杂度推导：如何从递推式证三种复杂度情况

核心前提：递推式里的θ(n)是什么 #

递推式 T(n) = 2T(n/2) + θ(n) 中，θ(n) 对应合并两个子数组的总操作时间，其中关键变量是关键字比较次数，元素移动的时间是固定O(n)，不影响复杂度阶数。三种情况的差异本质是合并阶段比较次数的不同，但最终复杂度阶数一致，下面逐个拆解：

1. 最坏情况：比较次数拉满 #

当两个子数组的元素完全交叉时（比如[1,3,5]和[2,4,6]），合并时每一步都要比较两个子数组的当前元素，直到其中一个子数组被耗尽，剩下的元素直接追加。

• 合并两个长度为k的子数组，最坏比较次数是 2k - 1（每个元素都要比一次，最后只剩一个元素无需比较）。
• 递推推导：设最坏时间复杂度为T_w(n)，则：

  T_w(n) = 2T_w(n/2) + n - 1  // 因为k=n/2，2*(n/2)-1 = n-1
  // 反向代入到n=1：
  T_w(n) = 2^k T_w(1) + k*n - (2^k - 1)  // k=log₂n，2^k=n
  = n*θ(1) + nlog₂n - (n-1)
  = θ(nlogn)
  

2. 最优情况：比较次数最少 #

当其中一个子数组的所有元素都小于等于另一个子数组的所有元素时（比如[1,2,3]和[4,5,6]），合并时只需要比较k次（较短子数组的长度，这里k=n/2），剩下的元素直接追加。

• 合并两个长度为k的子数组，最优比较次数是 k。
• 递推推导：设最优时间复杂度为T_b(n)，则：

  T_b(n) = 2T_b(n/2) + n/2
  // 反向代入到n=1：
  T_b(n) = n*θ(1) + sum_{i=0}^{k-1} n/2  // k=log₂n，sum部分是 (log₂n)*(n/2)
  = θ(n) + θ(nlogn)
  = θ(nlogn)
  

  这里注意：虽然比较次数少，但递归深度还是log₂n层，每一层总操作量仍是θ(n)，所以复杂度阶数不变。

3. 平均情况：基于概率的推导 #

平均情况需要考虑所有可能的输入排列，计算合并阶段的平均比较次数。对于两个长度为k的有序子数组，平均比较次数是 2k - 2k/(k+1)（推导基于所有元素排列的等概率假设，最终结果是θ(k)）。

• 对应的递推式为 T_avg(n) = 2T_avg(n/2) + θ(n)，和最坏/最优情况的递推式阶数一致，用反向代入法或主定理可直接得出 T_avg(n) = θ(nlogn)。

为什么三种情况复杂度都是θ(nlogn)？ #

归并排序的分治结构决定了递归深度固定为log₂n，每一层的总合并操作量（不管比较次数多少）都是θ(n)。最坏情况的常数因子比最优情况大，但从渐近复杂度的角度，它们属于同一个阶——θ(nlogn)。这也是归并排序的优势：无论输入是否有序，时间复杂度都稳定在θ(nlogn)。

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