如何推导归并排序代码的递推关系并使用Master定理计算时间复杂度

• 首先明确：不需要精确统计每一行代码的操作数，只需要区分递归调用部分和非递归的额外操作部分的时间量级即可，大O复杂度表示会忽略常数系数和低阶项，逐行统计操作数没有必要。

步骤1：推导对应递推关系 #

设T(n)为对长度为n的数组执行归并排序的时间开销，结合代码逐段分析：

1. 边界条件：当数组长度n ≤ 1时，无需拆分合并，仅执行打印等常数时间操作，因此T(n) = O(1)
2. 当n > 1时，开销分为三个部分：
   • 拆分操作：代码中alist[:mid]和alist[mid:]两个切片操作的时间和切片总长度成正比，合计为O(n)
   • 递归调用：两次调用mergeSort分别处理长度为n/2的左右子数组，合计开销为2*T(n/2)
   • 合并操作：后续三个while循环总共只会遍历n个元素完成合并，没有嵌套循环，开销为O(n)
   • 打印等其他操作均为常数级或线性级，不会改变整体量级
     因此最终的递推关系为：
     T(n) = 2T(n/2) + O(n)

步骤2：应用Master定理求解复杂度 #

Master定理适用于求解形如T(n) = aT(n/b) + f(n)（a≥1，b>1）的分治递推式，代入我们得到的参数：

• a = 2，对应递归调用的次数
• b = 2，对应每次递归数据规模缩小的倍数
• f(n) = O(n)，对应递归外的额外操作开销

首先计算基准值：n^log_b a = n^log_2 2 = n^1 = O(n)
对比可得f(n)和n^log_b a属于同一量级，符合Master定理的第二种情况，因此最终时间复杂度为：
T(n) = O(n * log n)

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