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

Question

我遇到作业问题：

which of these is an asymptotically tight upper bound for the best-case running time of an optimal algorithm that finds the maximum element in an arbitrary array of integers of size n

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

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

Answer 1

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

假设我 运行 你的算法在某个数组 A₁ 上只包含数字 0。因为你的算法不查看数组中的所有位置数组，有一些位置它没有看；称那个位置为k。现在，定义 A₂ 为与数组 A₁ 相同的数组，除了 A[=23= 中位置 k 处的元素]2定义为1.

现在，如果我 运行 你的算法在 A₂ 上会怎样？由于您的算法从未查看 A₁ 中的位置 k 并且 A₂ 与 A₂ 相同，除了在位置 k，您的算法无法区分 A₁ 和 A₂。因此，无论它对 A₁ 说什么，都必须与它对 A₂.

说的一样

不过这是个问题。如果你的算法说最大值是0，那么A₂是错误的，它的最大值是1。如果你的算法说最大值是1，那么A[=是错误的。 =23=]1，其最大值为0。因此，该算法至少有一种情况是错误的，所以它不可能是求最大值的正确算法。

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

希望对您有所帮助！

Answer 2

如果我们对数组中的数据一无所知，

O(n) 就是 运行 的时间。在你的情况下这是真的。 "an arbitrary array of integers of size n" 意味着它可以是任何整数数组。

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