NOIP 普及组初赛 · NOIP 2017 普及组初赛试题 第 17 题

设 $A$ 和 $B$ 是两个长为 $n$ 的有序数组，现在需要将 $A$ 和 $B$ 合并成一个排好序的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做（ ）次比较。

两个各有n个元素的有序数组合并，最坏情况下每次只确定一个元素的位置，需要2n−1次比较。因为比较完2n−1次后最后一个元素不用比了。

⚠️ 不要和归并排序的总复杂度 n log n 搞混！这里问的是"两个有序数组合并"这一步的最坏比较次数。最好情况是其中一个数组的最大值小于另一个的最小值→只需n次比较。最坏情况是穿插交替：A1<B1<A2<B2<... 每确定一个元素都要比较一次，最后一个不用比→2n−1。

合并两个有序数组

两个长度各为 n 的有序数组 A 和 B，合并成一个长度为 2n 的有序数组。

每次比较 A[i] 和 B[j]，较小的那个放入结果数组。

最坏情况

最坏情况是 A 和 B 的元素交替出现：A₁ < B₁ < A₂ < B₂ < … < Aₙ < Bₙ

每次比较只能"淘汰"一个元素。一共 2n 个元素，确定前 2n−1 个元素各需要 1 次比较，最后一个元素不需要比较（剩谁就是谁）。

最坏比较次数 = 2n − 1

最好情况

如果 A 的所有元素都小于 B 的最小元素（或反过来），比较 n 次即可（一个数组全部比完，另一个直接复制）。

选项分析

• A. n² ❌ 太离谱
• B. n log n ❌ 这是归并排序的总复杂度，不是合并这一步
• C. 2n ❌ 多了一次
• D. 2n−1 ✅