CSP-S 2022 第一轮 第14题：以比较为基本运算，在n个数的数组中找最大的数，在最坏情况下至少要做（）次运算。

题目

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

选项

• A. n/2
• B. n-1
• C. n
• D. n+1

答案

B

题解

选 B. \(n-1\)。

可以先把第一个数当作最大值，再依次与剩下的 \(n-1\) 个数比较，遇到更大的数就更新最大值。这样共需 \(n-1\) 次比较。

为什么不能更少？每次比较最多排除一个“最大值候选者”。要从 \(n\) 个候选者中确定一个最大值，就必须排除其余 \(n-1\) 个，所以至少需要 \(n-1\) 次比较。