CSP-J 入门级 · CSP 2021 入门级第一轮 第 4 题

以比较作为基本运算，在 $N$ 个数中找出最大数，最坏情况下所需要的最少的比较次数为 （ ）。

这题别想复杂了，直接想最朴素的做法：先假设第一个数是最大，然后拿它跟后面剩下的 N-1 个数一个个比，只要发现更大的就立刻换。这种‘线性扫描’就是最优解，不需要任何排序或分治技巧。

最容易掉进两个坑：一是把找最大值当成排序，以为要 O(N²) 或 O(N log N)，其实排序是找最大值的‘过度设计’；二是数学直觉偏差，认为 N-1 次不够，非得搞 N+1 次（比如想先两两配对再汇总），或者误以为每个数都要和最大值比一次。记住核心逻辑：除最大值外，其余 N-1 个数各至少被比较一次就能被排除，不可能更少。

考察知识点：基础算法 / 排序基础（找最大值是排序思想的最简形式）

命题视角：命题人爱在这里挖‘过度设计’的坑。学生一看到 N 个数，下意识想冒泡、想快速排序，结果把复杂度搞到 N² 或 N log N，完全跑偏。其实题目只要求‘找出最大数’，这是最基础的线性扫描，复杂度就是 O(N)，比较次数固定为 N-1。命题人就是想看看你是否能区分‘排序’和‘找极值’，以及是否理解‘下界’的概念——每个非最大元素至少参与一次比较才能被证伪。

思考心法：拿到题先想最朴素的做法，别追求花哨。假设第一个数 a[0] 是当前最大值 max，然后从 a[1] 开始，依次和 max 比：如果 a[i] > max，就更新 max = a[i]。循环跑完整个数组，max 就是答案。这个过程中，a[0] 参与了 N-1 次比较（被后面每个数都比一次），而 a[1] 到 a[N-1] 每个数只参与了 1 次比较（要么和当前 max 比，要么直接跳过）。所以总比较次数就是 N-1。

为什么 N-1 是最优下界：除了最大值本身，其他 N-1 个数都必须是‘输家’，也就是说，每个输家至少有一次比较证明它比某个数小。如果某个数从来没和最大值比过，你怎么知道它不是最大值？所以至少需要 N-1 次比较。这不仅是算法实现的结果，更是理论下界，任何正确算法都不能少于 N-1 次。

避坑提醒：别被选项 A 的 N² 迷惑，那是冒泡排序两遍扫描的总量，跟找最大值无关；别选 D 的 N+1，那是数学直觉偏差，以为要额外比一次；也别选 B 的 N，那是把最大值自己也算进比较次数里了，但最大值不需要‘证明’自己最大，它天然就是候选。记住：N-1 是精确答案。

考频与趋势：从题库数据看，‘排序基础’是绝对高频考点，249 题覆盖 9 个级别，年份分布极不均匀——2026 年高达 50 题，2025 年 57 题，2024 年 51 题，2023 年更是 22 题，说明近四年命题组明显加大了基础算法的考查力度。分赛事看，GESP 五级（74 题）和 CSP 入门级（44 题）是主力战场，NOIP 提高组初赛（12 题）也有稳定产出。这题作为 CSP 入门级第 4 题，正好卡在‘基础但易错’的位置，符合入门级‘先会做再会优化’的命题节奏。

预测：基于近四年数据，基础算法题（尤其是线性扫描、贪心思想）在 CSP 入门级和 GESP 五级的占比将持续上升，预计 2027 年这类题还会保持高位。命题人可能会继续用‘找最大值/最小值’这种极简场景来测试学生对‘下界’的理解，或者稍微包装成‘数组去重后找最大’‘动态更新最大值’等变体，但核心比较次数 N-1 的逻辑不会变。暂无足够依据预测具体年份的题量变化，只能肯定：只要还在考基础算法，这题的变体就永远有戏。