NOIP 提高组初赛 · NOIP 2016 提高组初赛试题 第 5 题

以比较作为基本运算，在 $N$ 个数中找最小数的最少运算次数为（ ）。

拿到这题别想复杂算法，直接抓住“比较”这个动作的本质：每比一次，就能把其中一个数从“可能是最小”的候选名单里坚决剔除。N 个数里要留下一位冠军，必须淘汰掉 N-1 位选手，所以最少比较次数就是 N-1。

最容易掉进命题人设的陷阱是选 A（N）。很多学生惯性思维觉得要比较 N 次，其实把第一个数默认当作最小值，后面 N-1 个数只要跟它比一次就能淘汰，多比一次纯属浪费。还有人选 D（log N），那是二分查找或合并排序的复杂度，跟“找最值”的线性扫描完全不是一回事，别被其他算法的术语带偏了。

考点概念：比较与淘汰的线性本质

这道题考的是最值查找在比较模型下的下界。

命题视角：为什么是 N-1？

命题人想让你透过复杂的算法外壳，看到最朴素的逻辑：

• 在 N 个数中找最小数，本质上是要确定一个“冠军”。
• 每一轮比较，必然产生一个胜者（保留）和一个败者（淘汰）。败者就永远不可能是最小值了。
• 要让 N 个候选者只剩下一个，必须淘汰掉 N-1 个。
• 因为每轮最多淘汰一个，所以最少需要 N-1 轮比较。

这就是为什么选项 A（N）是错的——你只需要 N-1 次比较就能把 N-1 个“非最小”都踢出去，多比一次毫无意义。