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

Question

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

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

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

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

Answer 1

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

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

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

不过，这是个问题。如果你的算法说最大值是0，那么A ₂是错误的，它的最大值是1。如果你的算法说最大值是1，那么A ₁是错误的，它的最大值是0。因此，算法至少在一种情况下必须是错误的，因此它不能是找到最大值的正确算法。

这个论点表明，任何总是在数组中找到最大值的确定性算法都必须查看该数组中的所有位置，因此运行时间必须是 Ω(n) 才能正确。

希望这可以帮助！

Answer 2

如果我们对数组中的数据一无所知，则 O(n) 是运行时间。在你的情况下是真的。“大小为 n 的任意整数数组”意味着它可以是任何整数数组。

当数组被排序时，O(1) 是可能的。如果我们首先使用快速排序对数组进行排序，然后选择最大的项目，则 O(nlog n) 是可能的。如果我们首先使用冒泡排序对数组进行排序，然后只选择最大的项目，则 O(n^2) 是可能的。