寻找数组最大元素的最好与平均时间复杂度疑问及与顺序搜索的对比

数组最大元素查找的时间复杂度 #

• 最好情况：O(n)。哪怕数组第一个元素就是最大值，你也必须遍历并比较完所有元素——只有确认后面没有更大的元素，才能确定它是整个数组的最大值，不存在提前终止的可能。对包含n个元素的数组，需要做n-1次比较，时间复杂度为线性O(n)。
• 平均情况：O(n)。无论数组元素如何分布，该算法都得完整遍历数组，平均比较次数固定为n-1次，时间复杂度仍为O(n)。

与顺序搜索的核心差异 #

顺序搜索的逻辑是找到目标值后立即停止，因此两者的时间复杂度表现有明显区别：

• 顺序搜索的最好情况是O(1)：如果目标值恰好位于数组第一个位置，仅需1次比较就能完成搜索。
• 顺序搜索的平均情况是O(n)：假设目标值在数组各位置出现概率均等，平均需要进行(n+1)/2次比较，虽然时间复杂度仍为线性，但实际执行的操作次数通常少于找最大元素的算法。

为何最坏情况时间复杂度相同？ #

两者的最坏情况均为O(n)，原因很直接：

• 找最大元素的算法本身要求遍历完整个数组，这是确定最大值的必要步骤，没有例外。
• 顺序搜索的最坏情况有两种：目标值在数组最后一个位置，或者目标值不存在于数组中——这两种情况都需要遍历完所有元素才能得出结论。
  因此，两者在最坏情况下都需要执行n次左右的操作，时间复杂度均为线性O(n)。

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