NOIP 提高组初赛 · NOIP 2014 提高组初赛试题 第 15 题

以下程序实现了找第二小元素的算法。输入时 $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];
		}

这道题考的是找第二小元素的算法复杂度，特别是嵌套条件语句在最坏情况下的比较次数。拿到题先别急着套公式，顺着代码走一遍：先比 S[1] 和 S[2] 定好两个基准，然后从 S[3] 开始一个个往里插。最坏情况就是每次进来都比两个基准小，这时候内层 if 也会触发，每轮就多了两次比较。把这种‘每次都撞墙’的情形拎出来算总数，就能稳稳选对。

最容易掉进的坑是以为只有外层比较，直接算成 n-1 次，或者把初始那一步漏掉。其实每轮循环里，先判断 S[i] 是否小于 SecondMin，如果小于再判断是否小于 FirstMin，这两个判断是串行的，最坏情况下两个都会执行。另外，很多人会忽略题目强调的‘最坏情况’，只考虑平均或最好情况，导致选错。还有，有人会误以为 SecondMin 更新后不再参与后续比较，实际上 SecondMin 在每一轮都是当前已扫描部分中的第二大值，后续元素依然可能比它小，所以必须一直保留这个变量。

找第二小元素算法分析

题目考查什么

这道题考查的是找第二小元素算法的时间复杂度，特别是嵌套条件语句在最坏情况下的比较次数。在信息学竞赛初赛里，这种题目很常见：给一段代码，让你判断它在最坏情况下做了多少次比较。这类题不仅考你读代码的能力，还考你对算法逻辑的理解——你得知道什么时候比较次数会达到峰值。