NOIP 提高 2017 第一轮 第 11 题：设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排

题目

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

选项

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

答案

D

题解

考点定位

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

解题过程

最坏 2n−1 次。

选 D。

易错提醒

① 与普及组同题；② 交错输入构造最坏。