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

Question

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

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

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

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

Answer 1

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

假设我在某个只包含数字 0 的数组 A ₁上运行你的算法。由于你的算法不会查看数组中的所有位置，因此它不会查看某些位置；将该位置称为 k。现在，将 A _{2定义为与数组 A 1}相同的数组，只不过 A ₂中位置 k 的元素被定义为 1。

_{现在，如果我在 A 2}上运行你的算法会发生什么？由于您的算法从未查看过 A ₁中的位置 k ，并且除了位置 k 之外，A _{2与 A 2}相同，因此您的算法无法区分 A ₁和 A ₂。_{因此，对于 A 1 的}描述必须与对于 A ₂的描述相同。

但这是一个问题。如果你的算法说最大值是 0，那么对于 A ₂来说是错误的，其最大值是 1。如果你的算法说最大值是 1，那么对于 A ₁来说是错误的，其最大值是 0。因此，该算法至少在一种情况下肯定是错误的，因此它不可能是寻找最大值的正确算法。

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

希望这可以帮助！