数组查找最小值的朴素算法：最优/最坏情况比较次数疑问

你的结论是对的 #

你写的这段代码，不管数组是升序、降序还是乱序，比较次数都是固定的 n-1（n 为数组长度）。原因很直接：

• 循环从第 2 个元素（索引 1）遍历到最后一个元素，一共执行 n-1 次
• 每次循环里，arr[i] < temp 这个比较操作是必做的，你把 comparisons++ 放在判断前，刚好准确统计了每一次比较——不管判断结果是真还是假，只要执行了就计数
• 要确定当前的 temp 是全局最小值，必须遍历完所有后续元素，所以总比较次数固定为 n-1

你朋友的说法是混淆了其他场景 #

他提到的「最坏情况 2(n-2)+1 次、最优 n-1 次」，大概率是把这个问题和同时查找最大值和最小值的算法搞混了：

• 同时找最大最小的算法中，最坏情况确实需要 2n-3 次比较（也就是 2(n-2)+1），因为每次循环可能需要两次判断（先比最大值，再比最小值）
• 另外，也有可能他设想了错误的计数方式——比如只在 arr[i] < temp 条件成立时才计数，但这不符合逻辑：只要执行了 < 判断，不管结果如何，这都是一次比较操作，必须算入次数统计

补充：正确的比较次数统计逻辑 #

统计算法的比较次数时，每执行一次关系判断（比如 <、>、==）就算一次比较，和判断结果无关。你的代码完全符合这个逻辑，统计结果是准确的。

内容的提问来源于stack exchange，提问作者Techie5879