CSP-S 2024 第一轮 第2题：假设一个长度为n的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个

题目

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

选项

• A. $O(n)$
• B. $O(\log n)$
• C. $O(n \log n)$
• D. $O(1)$

答案

A

题解

选 A. \(O(n)\)。

从头到尾遍历一次数组，用变量 max 记录目前找到的最大值：

1. 将第一个元素设为 max。
2. 依次比较后面的元素，遇到更大的就更新 max。
3. 遍历结束后，max 就是数组中的最大元素。

总共需要比较 \(n-1\) 次，因此时间复杂度为 \(O(n)\)。

因为数组无序，任何一个没查看的元素都可能是最大值，所以必须检查所有元素。