是否存在在 O(log n) 时间内找到未排序数组的最大值的算法？
问问题
28863 次
9 回答
25
这个问题被问了很多（这是一个流行的 CS 作业问题还是什么？），答案总是一样的：不。
从数学上考虑。除非对数组进行排序，否则没有什么可以“切成两半”来给你log(n)行为。
阅读问题评论以进行更深入的讨论（无论如何这可能超出了问题的范围）。
于 2012-09-15T20:33:06.197 回答
10
考虑一下：如果不访问每个元素，你怎么知道你没有访问过的某个元素不大于你迄今为止找到的最大元素？
于 2012-09-15T20:38:13.970 回答
6
在 中无法做到这一点O(log(N))。这是O(N)最好/最坏/平均的情况，因为需要访问数组中的每个项目以确定它是否是最大的。数组未排序，这意味着您不能偷工减料。
即使在并行化的情况下，这也不能在 中完成O(N)，因为Big-O表示法不关心一个 CPU 有多少或每个 CPU 的频率是多少。它是专门从这个抽象出来的，以给出问题的粗略估计。
可以忽略并行化，因为可以认为划分作业所花费的时间等于顺序执行的时间。这是由于忽略了常数的原因。以下都是一样的：
O(N) = O(Const * N) = O(N / Const) = O(N + Const) = O(N - Const)
另一方面，在实践中，分治并行算法可以为您带来一些性能优势，因此它可能会运行得更快一些。幸运的是，Big-O不处理这种细粒度的算法复杂性分析。
于 2012-09-16T12:25:22.243 回答
4
不。您必须至少遍历数组一次。
于 2012-09-15T20:31:09.613 回答
4
不，它是 O(n)。在最坏的情况下，必须访问和比较数组的所有成员。
于 2012-09-15T20:32:13.857 回答
1
当然不是 。假设还有一个元素，您还没有将它与任何其他元素进行比较。所以不能保证你没有比较的元素不是最大元素
并假设您的比较图（元素的顶点和比较的边）具有多个组件。在这种情况下，您必须放置一条边（以最好的方式在最多两个组件之间）。我们可以看到，在 n-1 操作必须完成
于 2014-05-13T12:34:27.577 回答
-1
这是很老的，但我不同意给出的答案。是的，它可以用并行硬件在对数时间内完成。
时间复杂度为：
O(log(n) * log(m))
n是要比较的数字的数量；m是每个数字的大小。
但是，硬件大小将是：
O(n * m)
该算法将是：
成对比较数字。时间为
O(log(m))，大小为O(n * m)，使用进位超前比较器。使用 1 中的结果来复用 1 的两个输入。时间为
O(1)，大小为O(n * m)。现在你有一个初始大小一半的数组；转到步骤 1。此循环重复
log(n)多次，因此总时间为O(log(n) * log(m))，总大小为O(n * m)。
如果需要，添加更多 MUX，您还可以跟踪最大数字的索引，而不会增加算法的复杂性。
于 2018-03-31T17:10:46.223 回答
-1
如果你使用N处理器，它可以及时完成O(log N)。但工作复杂度仍然存在O(N)。
如果使用N^2处理器，您可以O(1)通过应用Usain Bolt 算法来降低时间复杂度。
于 2018-08-09T04:02:58.020 回答
-1
我认为使用 Segment tree 可能会有所帮助，您可以实现 log(N) 成本。
于 2019-03-20T17:10:20.890 回答