寻找数组最大值的O(log n)算法？

Question

寻找数组最大值的O(log n)算法？

algorithmbig-o

17

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

- Takkun

1

@amit 因此需要“非常大的核心/处理器数量”。即当 k > n 时。 - Mysticial

2

@amit 使用你的公式，当 n == k 时会发生什么？n/n + log(n) = 1 + log(n) = log(n)。因此，如果你有 n 个核心（实际上 n/2 个核心就足够了），你可以获得 O(log(n))。尽管你可能需要添加一个并行化开销项（处理器之间通信的延迟）。 - Xantix

4

@Xantix，@Mystical：这是一个特例，其中核心数与元素数量成线性关系。传统上，在并行分析中，我们有两种选择：（1）将k视为某个常量，因此忽略它。（2）明确使用k符号。我从未看过任何一本书/文章分析算法时假设核心数k = f（n）为某个函数f（当然除了常数）。如果有人这样做了，请引用这个来源，我会撤回我的评论。 - amit

1

@Mystical，我认为线程分配复杂度仍然是O(n)，因此最终会得到O(n log n)。Brent定理可能有助于一些算法级联（证明并不简单），但也许我误解了这个概念。请参见http://www.uni-graz.at/~haasegu/Lectures/GPU_CUDA/Lit/reduction.pdf幻灯片30。 - David Titarenco

1

@DavidTitarenco：我不能针对这种情况发表意见，但我知道在排序网络中，复杂度明确地被限定为“大小”（与O（#processors x time complexity）相关）或“深度”（与O（time complexity）相关），因此我会推断出对于这个问题，如果充分限定，两者都是正确的想法。http://en.wikipedia.org/wiki/Sorting_network - Mooing Duck

显示剩余10条评论

12个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Franklin Zhao · Answer 1

如果您使用N个处理器，可以在O(log N)的时间内完成。但是工作复杂度仍然是O(N)。

如果使用N^2个处理器，可以通过应用Usain Bolt算法将时间复杂度降低到O(1)。

- ibrahim · Answer 2

我认为使用线段树可能会很有帮助，你可以实现log(N)的成本。