CSP-S 提高级 · CSP 2024 提高级第一轮 第 2 题

假设一个长度为 $n$ 的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（ ）

拿到题先看清‘无序’二字，直接想到必须遍历所有元素才能确定最大值，这就是 O(n) 的本质，其他选项要么需要有序条件要么多此一举。

学生最容易把‘找最大值’和‘排序’搞混，误以为要排好序才能找，结果选了 O(n log n)；或者看到 O(log n) 就条件反射想到二分，忘了二分的前提是有序；还有人会纠结‘互不相同’这个条件，以为能省步骤，其实互不相同只是保证最大值唯一，不影响遍历次数。

这道题考的是基础算法里的时间复杂度分析，尤其是线性扫描与二分、排序的区分。

先把概念捋直：时间复杂度就是算法运行时间随输入规模 n 增长的趋势，用大 O 表示上界。大 O 只看增长最快的项，常数系数和低阶项都忽略。比如 n-1 次比较，n 很大时 n-1 和 n 一样快，所以记作 O(n)。

命题人挖坑的点很明确：题目特意强调‘无序’且‘元素互不相同’。无序意味着不能二分；互不相同只是说明最大值唯一，不改变遍历次数。学生常掉进‘有序数组找最大值是 O(1)'的陷阱，但这里数组无序，必须逐个看。

思考心法：拿到题先问‘每个元素都要看一眼吗？’要。那就至少 O(n)。能不能跳着看？不能，因为不知道谁最大。能不能排序后直接取？能，但排序本身要 O(n log n)，题目只问找最大值，不用排序，所以 O(n log n) 是多余操作。

具体怎么算：初始化 max = arr[0]，从第 2 个元素开始，依次和 max 比较，若更大则更新。无论数组怎么排，都要走 n-1 次比较，常数项忽略后就是 O(n)。

避坑指南：别把‘找最大值’和‘排序’混为一谈。找最大值只需一次遍历 O(n)，排序需要 O(n log n)。也别被 O(log n) 诱惑，二分查找要求有序，本题数组无序，二分无从下手。

考频与趋势：基础算法在题库共考过 30 题，覆盖 3 个考试级别（2007-2025），逐年分布为：2007 年 2 题、2008 年 1 题、2009 年 4 题、2010 年 4 题、2011 年 5 题、2012 年 1 题、2013 年 1 题、2014 年 2 题、2016 年 1 题、2019 年 1 题、2021 年 4 题、2024 年 2 题、2025 年 2 题；分赛事为 NOIP 提高组初赛 13 题、CSP 提高级 9 题、NOIP 普及组初赛 8 题。这类线性扫描找极值的题目在 CSP 提高级和 NOIP 初赛反复出现，属于高频考点。

预测：基于现有数据，基础算法仍将是初赛必考内容，未来大概率继续以‘无序数组找最大值/最小值’这类简单线性扫描题出现，难度不会突变，但可能会结合其他小陷阱（如空数组、重复元素等）来增加区分度。暂无足够依据预测具体年份或题型变化，保持对线性扫描的熟练度即可。