合并两个长度为n和m的已排序数组的最坏运行时间疑问

先直接给结论：合并两个长度为n和m的已排序数组，时间复杂度固定是O(n + m)——不管是最坏还是最好情况，因为你必须处理完所有n+m个元素才能完成合并。

为什么O(n*m)不对 #

O(n*m)是暴力比对所有元素对的时间复杂度，比如在未排序数组里找交集的笨办法。但数组已经有序的情况下，我们用双指针法就能线性完成合并：

• 两个指针分别指向两个数组的起始位置
• 每次比较指针指向的元素，把更小的放进结果，移动对应指针
• 其中一个数组遍历完后，直接把另一个数组剩下的元素全追加进去
  整个过程每个元素只碰一次，总操作数就是n+m，完全到不了n*m的量级。

为什么O(max(n,m))不对 #

你可能觉得如果一个数组的元素全比另一个小，就能只遍历长数组？但合并的核心是要把所有元素都整合进去，哪怕数组A全是1，数组B全是100，你还是要把A的n个元素和B的m个元素都处理一遍，总操作数是n+m，而不是max(n,m)。不存在能跳过部分元素的合并方式——毕竟最终的合并数组得包含所有元素。

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