寻找最大元素的时间复杂度分析
我遇到了一个家庭作业问题：
其中哪一个是最佳算法最佳情况运行时间的渐近严格上限，该算法在大小为 n 的任意整数数组中查找最大元素
- O(log n)
- O(n2)
- O(n)
- O(1)
- O(n log n)
根据我的理解，它是 O(n) 因为即使这是最好的情况我们仍然需要 扫描 arr 以获得结果。请纠正我
I've encountered a homework problem:
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
- O(log n)
- O(n2)
- O(n)
- O(1)
- O(n log n)
Based on my understanding, it's O(n) since even it's the best-case we still need
to scan over the arr to get the result. Please correct me
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是的，这是正确的。看到这一点的一种方法是通过对抗性论证。假设您有一个算法，据称可以找到数组中的最大值，但不会至少检查每个数组元素一次。
假设我在某个只包含数字 0 的数组 A1 上运行您的算法。由于您的算法不会查看数组中的所有位置，因此它不会查看某些位置；将该位置称为 k。现在，将 A2 定义为与数组 A1 相同的数组，只不过定义了 A2 中位置 k 的元素为 1。
现在，如果我在 A2 上运行你的算法会发生什么？由于您的算法从未查看过 A1 中的位置 k，并且 A2 与 A2 相同（除了位置 k 之外），因此您的算法不能区分 A1 和 A2。因此，A1 的内容必须与 A2 的内容相同。
但这是一个问题。如果你的算法说最大值是 0，那么 A2 是错误的，其最大值是 1。如果你的算法说最大值是 1，那么 A1 是错误的，其最大值为0。因此，该算法至少在一种情况下是错误的，因此它不可能是寻找最大值的正确算法。
该参数表明，任何始终找到数组中最大值的确定性算法都必须查看该数组中的所有位置，因此运行时间必须为 Ω(n) 才正确。
希望这有帮助！
Yes, that's correct. One way to see this is via an adversarial argument. Suppose that you have an algorithm that allegedly finds the maximum value in the array, but doesn't inspect every array element at least once.
Suppose I run your algorithm on some array A1 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 A2 to be an array that's the same as array A1, except that the element at position k in A2 is defined to be 1.
Now, what happens if I run your algorithm on A2? Since your algorithm never looked at position k in A1 and A2 is identical to A2 except at position k, your algorithm can't tell A1 and A2 apart. Therefore, whatever it says for A1 must be the same as what it says for A2.
That's a problem, though. If your algorithm says that the maximum value is 0, then it's wrong for A2, whose max is 1. If your algorithm says that the maximum value is 1, then it's wrong for A1, 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.
This argument shows that any deterministic algorithm that always finds the maximum value in an array must look at all positions in that array, so the runtime must be Ω(n) to be correct.
Hope this helps!
如果我们对数组中的数据一无所知，则 O(n) 是运行时间。这对你来说是正确的。 “大小为 n 的整数的任意数组”意味着它可以是任何整数数组。
当数组已排序时，O(1) 是可能的。
如果我们首先使用快速排序对数组进行排序，然后选择最大的项，则 O(nlog n) 是可能的。
如果我们首先使用冒泡排序对数组进行排序，然后选择最大的项，则 O(n^2) 是可能的。
O(n) is the running time if we know nothing about the data in the array. Which in your case is true. "an arbitrary array of integers of size n" implies that it could be any integer array.
O(1) is possible when the array is sorted.
O(nlog n) is possible if we first use quicksort to sort the array and then select the largest item.
O(n^2) is possible if we first sort the array using bubblesort and then just select the largest item.