MIT《计算机科学与Python编程导论》：归并排序合并比较次数疑问

问题本质澄清 #

你实际计算的具体比较次数完全正确：合并两个长度为m和n的有序列表，最坏情况下确实需要m+n-1次比较，比如你举的例子——合并[1,3,5]（长度3）和[2,4]（长度2），实际需要4次比较，正好对应3+2-1=4。

课程里提到的“合并时仅需O(较长子列表长度)次比较”，是大O复杂度层面的简化表述，和你的理解并不冲突。

复杂度等价性说明 #

从大O的定义出发：

• 假设两个子列表长度分别为m和n，且m ≥ n（即m是较长子列表长度），那么m+n-1 ≤ 2m（因为n ≤ m，所以m+n ≤ 2m）。
• 根据大O的规则，常数系数可以忽略，因此O(m+n-1)等价于O(m)，也就是课程里说的O(较长子列表长度)。
• 同样，O(m+n)也和O(max(m,n))是等价的，因为两个子列表的总长度不会超过较长子列表长度的2倍。

不同场景的比较次数 #

• 最好情况：当其中一个列表的所有元素都小于另一个列表的所有元素时，比较次数等于较短子列表的长度。比如合并[1,2,3]和[4,5,6]，只需要3次比较。
• 最坏情况：就是你遇到的这种元素交替的有序列表，需要两个列表长度之和减1次比较。

但无论哪种情况，从复杂度量级的角度，用O(较长子列表长度)或者O(m+n)描述都是成立的，课程里的表述只是为了简化分析过程。

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