CSP-S 提高级 · CSP 2022 提高级第一轮 第 14 题

以比较为基本运算，在 n 个数的数组中找最大的数，在最坏情况下至少要做（ ）次运算。

这题考的是“找最大值至少需要多少次比较”的下界问题。拿到题先想：要把 n 个数里的最大值找出来，其他 n-1 个数每一个都必须至少输过一次比较才能被排除，所以直接数一下最少要排除几个数，答案就出来了。

最容易掉进两个坑：一是把初始化 max=a[0] 当成一次比较，其实那是赋值不是比较，所以 n 次是错的；二是看到“成对比较”就想到 n/2，那是并行模型或淘汰赛思维，顺序执行时每一步只能比两个数，无法同时排除多个，所以 n/2 也不对。

这道题考查的是基础算法中的比较下界问题，核心在于理解“排除法”的逻辑。在 n 个数的数组中找最大值，我们不需要把所有数两两比较，只需要让每个数都参与一次比较，并且确保除了最终最大值外，其他 n-1 个数都被证明“不是最大值”即可。因为每次比较最多只能排除一个数（输掉的那个），所以要排除 n-1 个非最大值，至少需要 n-1 次比较。这就是最坏情况下的下界，也是任何基于比较的算法都无法突破的极限。命题人喜欢在这里挖坑，一是混淆赋值与比较，二是引入并行思维，让学生误以为可以成对比较从而减少次数。思考心法很简单：拿到题先想“每个元素至少需要参与多少次比较才能完成目标”，然后数一下需要排除多少个元素。计算过程就是 n-1，因为从第二个数开始，依次和当前最大值比较，共 n-1 次。避坑提醒：n 次多算了一次初始化，n/2 次是并行模型，都不符合顺序比较的实际情况。考频趋势显示，排序基础在 CSP 提高级中占比 9 题，虽然不算高频，但每年都有出现，尤其是近年趋势明显上升，2025 年 57 题、2026 年 50 题，说明这类基础下界问题依然是必考点。暂无足够依据预测未来具体年份的考法，但可以肯定的是，这类题目会持续以不同形式出现，考察学生对算法下界的理解。