NOIP 提高 2014 第一轮 第 15 题：以下程序段实现了找第二小元素的算法。输入是n个不等的数构成的数组S，输出S中

题目

以下程序实现了找第二小元素的算法。输入时 $n$ 个不等的数构成的数组 $S$，输出 $S$ 中第二小的数 $\mathrm{SecondMin}$。在最坏的情况下，该算法需要做（   ）次比较。

if ( S[1] < S[2] )
{
	FirstMin	= S[1];
	SecondMin	= S[2];
} else {
	FirstMin	= S[2];
	SecondMin	= S[1];
}
for ( i = 3; i <= n; i++ )
	if ( S[i] < SecondMin )
		if ( S[i] < FirstMin )
		{
			SecondMin	= FirstMin;
			FirstMin	= S[i];
		} else {
			SecondMin = S[i];
		}

选项

• A. 2n
• B. n-1
• C. 2n-3
• D. 2n-2

答案

C

题解

考点定位

本题考「第二小元素比较次数」,对应大纲 4.1.1 复杂度（难度【4】）。

解题过程

题给实现：先比较前两个元素定当前最小/第二小（1 次），再对每个新元素与最小、第二小各比一次（2 次/个），共 (n−2)×2+1 = 2n−3 次。

选 C。

易错提醒

① 逐元素「两连比」的策略；② 理论最优（淘汰树法）是 n+⌈log₂n⌉−2，但题目问「该算法」的次数。