用于查找数组最大值的O(log n)算法？

Question

是否存在在O(log n)时间内找到未排序数组的最大值的算法？

Answer 1

这个问题被问了很多(这是一个流行的CS家庭作业问题还是什么？)答案总是一样的:不.

用数学的方式考虑一下.除非对数组进行排序,否则没有什么可以"减半"来为您提供log(n)行为.

阅读问题评论以进行更深入的讨论(无论如何,这可能超出了问题的范围).

Answer 2

考虑一下:如果不访问每个元素,你怎么知道你没有访问过的元素不大于你到目前为止找到的最大元素？

Answer 3

这是不可能的O(log(N)).它O(N)处于最佳/最差/平均情况,因为需要访问数组中的每个项目以确定它是否是大数据.数组未排序,这意味着您不能偷工减料.

即使在并行化的情况下,也无法做到这一点O(N),因为Big-O表示法并不关心每个CPU有多少CPU或每个CPU的频率.它是专门从这个中抽象出来的,以便给出问题的原始内容.

可以忽略并行化,因为划分作业所花费的时间可以被认为等于顺序执行的时间.这是由于常数被忽视的原因.以下是完全相同的:

O(N) = O(Const * N) = O(N / Const) = O(N + Const) = O(N - Const)

另一方面,在实践中,分而治之的并行算法可以为您带来一些性能优势,因此可以更快地运行.幸运的是,Big-O没有处理这种细粒度的算法复杂性分析.