NOIP 普及 2017 第一轮 第 17 题：合并两个有序数组的最坏比较次数

题目

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

选项

• A. $n^{2}$
• B. $n \log n$
• C. $2n$
• D. $2n - 1$

答案

D

题解

考点定位

本题考「归并比较下界」,对应大纲 4.1.1（难度【3】）。

解题过程

两长 n 有序数组合并最坏比较 2n−1 次（交错输出，最后一次免比较）。

选 D。

易错提醒

① 与 2019 年同题；② 最好情形 n 次（一数组整体小）。