寻找最大元素的时间复杂度分析

我遇到了一个家庭作业问题：

其中哪一个是最佳算法最佳情况运行时间的渐近紧上限，该算法在任意大小的整数数组中查找最大元素n

1. O(log n)
2. O(n²)
3. O(n)
4. O(1)
5. O(n log n)

根据我的理解，它是 O(n) 因为即使这是最好的情况我们仍然需要 扫描 arr 以获得结果。请纠正我

对，那是正确的。看到这一点的一种方法是通过对抗性论证。假设您有一个算法，据称可以找到数组中的最大值，但不会至少检查每个数组元素一次。

Suppose I run your algorithm on some array A₁ that consists of nothing but the number 0. Since your algorithm doesn't look at all positions in the array, there's some position it doesn't look at; call that position k. Now, define A₂ to be an array that's the same as array A₁, except that the element at position k in A₂ is defined to be 1.

Now, what happens if I run your algorithm on A₂? Since your algorithm never looked at position k in A₁ and A₂ is identical to A₂ except at position k, your algorithm can't tell A₁ and A₂ apart. Therefore, whatever it says for A₁ must be the same as what it says for A₂.

That's a problem, though. If your algorithm says that the maximum value is 0, then it's wrong for A₂, whose max is 1. If your algorithm says that the maximum value is 1, then it's wrong for A₁, whose max is 0. Therefore, the algorithm has to be wrong in at least one case, so it can't be a correct algorithm for finding the maximum value.

该参数表明，任何始终找到数组中最大值的确定性算法都必须查看该数组中的所有位置，因此运行时间必须为 Ω(n) 才正确。

希望这可以帮助！