CSP-J 2021 第一轮 第 4 题：找最大数最坏情况最少比较次数

题目

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

选项

• A. $N^{2}$
• B. $N$
• C. $N-1$
• D. $N+1$

答案

C

题解

答案是 C. \(N-1\)。

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

为什么不能更少？因为要确定最大数，其余 \(N-1\) 个数都必须至少“输”过一次比较，才能排除它们是最大数的可能。每次比较最多排除一个候选，所以至少需要 \(N-1\) 次比较。