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

Question

我遇到了一个作业问题：

对于一种在任意大小的整数数组中找到最大元素的最优算法的最好情况运行时间，以下哪个渐近紧密的上界是正确的？

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

根据我的理解，答案应该是 O(n)，因为即使是最好情况下，我们仍然需要扫描整个数组来获取结果。请纠正我。

- Fihop

Answer 1

是的，没错。可以通过一个对抗论证来看待这个问题。假设你有一个算法，声称在数组中找到最大值，但不检查每个数组元素至少一次。

假设我在某个仅由数字 0 组成的数组 A1 上运行你的算法。由于你的算法没有查看数组中的所有位置，因此有些位置它没有查看；将该位置称为 k。现在，定义一个数组 A2，与数组 A1 相同，除了 A2 中位置k的元素被定义为 1。

现在，如果我在 A2 上运行您的算法会发生什么？由于你的算法从未查看过 A1 中的位置 k，而 A2 除了在位置 k 处与 A1 不同外，它们是相同的，所以你的算法无法区分 A1 和 A2。因此，无论它说 A1 的结果如何，它必须与它说 A2 的结果相同。

但这是个问题。如果你的算法说最大值是 0，则对于 A2，最大值是 1，那就是错的。如果你的算法说最大值是 1，则对于 A1，最大值是 0，那也是错的。因此，算法必须在至少一种情况下是错误的，因此它不能是正确的找到最大值的算法。

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

希望这有所帮助！

- templatetypedef

Answer 2

如果我们对数组中的数据一无所知，那么运行时间为O(n)，在您的情况下也是如此。"大小为n的任意整数数组"意味着它可以是任何整数数组。

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

- Jaspreet Singh

---

你说：“如果我们先使用快速排序对数组进行排序，然后选择最大项，则可能是O(nlog n)。如果我们首先使用冒泡排序对数组进行排序，然后只选择最大项，则可能是O(n^2)。”是的，如果应用错误的算法，则可能出现高于O(n)的复杂度，但这不是在未排序的数组中查找最大值的复杂度。 - giuseppe