logo标签列表

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

algorithmbig-o
17

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

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个回答
26

这个问题被问得很多（这是一个常见的CS作业问题吗？），答案总是一样的：不行。

从数学上考虑。除非数组已经排序，否则没有什么可以“切成一半”来给你log(n)的行为。

阅读问题评论进行更深入的讨论（这可能超出了问题的范围）。

比特尼克数组是什么？我们如何在具有对数复杂度的数组中找到比特尼克数（最大数）？ - Prasanna
显然，这个问题涉及到并行计算，在这种情况下，它是完全可能的。 - Gregory Morse
10
考虑这个问题：如果没有访问每个元素，你怎么知道你没有访问过的某个元素不比你目前找到的最大元素还要大？
6
这在O(log(N))中是不可能完成的。因为需要访问数组中的每个项目才能确定它是否是最大的，所以在最好/最坏/平均情况下它是O(N)。由于数组未排序，因此无法抄近路。
即使在并行化的情况下，这也不能在O(N)内完成，因为大O符号表示并不关心一个人有多少CPU或每个CPU的频率是多少。它是从具体问题中抽象出来的，只能给出粗略的估计。
并行化可以被忽略，因为花费在分割作业上的时间可以视为顺序执行的时间。这是由于常数被忽略的原因。以下内容是相同的：
O(N) = O(Const * N) = O(N / Const) = O(N + Const) = O(N - Const)

另一方面，在实践中，分治并行算法可以带来一些性能上的好处，因此它可能会运行得更快。幸运的是，大O表示法不涉及这种细粒度的算法复杂度分析。

大O分析肯定涉及分治复杂性。如果您的并行性是n/2个比较同时进行，那么它将降低到O(log n)复杂度。如果n足够大，并且您实际上拥有如此荒谬数量的处理器，则细粒度点是完全无关紧要的。您将获得实际的时间节省。将工作分解可能是一次性任务，而计算可以重复多次。拥有大量专用处理器等待仅执行此任务并不特别现实，但在理论上和实践上是可能的。 - Gregory Morse
假设可以拥有一个N-Core超级计算机，那么可以假设将任务分配给每个核心，以便每个核心执行一些计算任务。这将使得这是一个O(1)的任务，只要我们不需要随后比较彼此之间的计算结果以找出最大值。比较是一个O(1)操作，但需要重复进行N次，因为没有办法不比较某些内容并仍然获得最大值。因此，无论核心数量如何，对于此任务来说，O(log n)都是不可能的。 - oleksii
1
这是不正确的，征服部分需要O(log n)步。锦标赛胜者算法意味着每一步只需要一半的比较次数。因此，首先在O(1)中比较n/2，然后在O(1)中比较n/4...直到只剩下1个，即最大值。这是原型化的log n算法。 - Gregory Morse
1
实际上，锦标赛算法完全适用于未排序的数组。[4, 1, 0, 22, 7, 3, 5] -> [4, 22, 7, 5] -> [22, 7] -> [22]。它不在乎它在哪里。[22, 4, 1, 0, 7, 3, 5] -> [22, 1, 7, 5] -> [22, 7] -> [22]。[4, 1, 0, 7, 3, 5, 22] -> [4, 7, 5, 22] -> [7, 22] -> [22]。我建议参加正式的算法课程。这就是我学到这个算法的地方。任何阶段的奇数都是锦标赛下一轮的“by” - 最终在递归关系中成为一个天花板函数。请记住，我们在这里谈论的是并行性！当然，这对于非并行也是正确的。 - Gregory Morse
1
@GregoryMorse 在这里不能简单地使用锦标赛选择，因为首先需要构建比赛。构建比赛的时间复杂度是O(n)。我很高兴就此打住：你认为你是对的，那就这样吧。 - oleksii
显示剩余2条评论
4

不行。你至少需要遍历一次数组。

4
不是O(1)，而是O(n)。在最坏情况下，必须访问并比较数组的所有成员。
1
当然不是。假设仍有一个元素未与任何其他元素进行比较。因此，无法保证您尚未比较的元素不是最大元素。
假设您的比较图（元素的顶点和比较的边缘）具有多个组件。在这种情况下，您必须将一条边（以最佳方式连接两个组件中的最大值）。我们可以看到，在进行n-1次操作时必须完成。
0

是的，我们可以这样做，但有一个条件，那就是我们的数组必须是山形数组。

public int peakIndexInMountainArray(int[] arr) {
    int s = 0;
    int e = arr.length-1;
    int mid = s+(e-s)/2;
    while(s<e){``
        if(arr[mid]<arr[mid+1]){
            s = mid+1;
        }
        else{
            e = mid;
        }
        mid = s+(e-s)/2;
    }
    return mid;
}`
0

O(log n) 意味着您甚至不必读取整个数组，因为那将是 O(n)，对于未排序的数组来说这并不真实，因为如果您无法将其与所有其他元素进行比较，则无法保证元素是否为最大值。 O(n) 是您可以获得的最佳绝对最大值，它仅遍历一次数组，如果您只想要一个近似值，则可以随机选择元素并拥有它们的最大值，这将选择少于 n 个元素，但对于未排序的数组而言，O(log n) 是不可能的。

0

有一种比 O(N) 更好的算法：

你只需要从数组中随机选择一个元素，并假设它是最大的。

不，说真的，如果你有一个正态分布的数字数组，并且你不需要得到最大的数字，而是一些接近最大的数字，那么你可以，比如说，随机选择 N/10 个元素并从中选择最大的。 对于正态分布，找到一个足够接近最大值的数字的机会是相当高的。或者你可能幸运地找到最大的数字，但你无法确定是否找到了。

我认为，在某些情况下，这种方法可能很有用。例如，如果你需要将数字分组到桶中，但又不想读取整个数组。在这种情况下，你可以随机选择10%的样本，并根据该样本的最大值加一个额外的桶来进行分组，用于存放超过该10%最大值的数字。这应该足够好了。

-1
这是非常古老的内容，但我不同意所给的答案。是的，使用并行硬件，可以在对数时间内完成。
时间复杂度将是：
O(log(n) * log(m))

n 是要比较的数字的数量；m 是每个数字的大小。

然而，硬件尺寸将是：

O(n * m)

算法如下：

  1. 成对比较数字。这需要的时间为O(log(m))，大小为O(n * m)，使用进位前瞻比较器。

  2. 使用步骤1的结果来复用1的两个输入。这需要的时间为O(1)，大小为O(n * m)。

  3. 现在你有一个初始大小的一半的数组；回到步骤1。这个循环重复log(n)次，所以总时间为O(log(n) * log(m))，总大小为O(n * m)。

通过添加一些MUX，您还可以跟踪最大数字的索引（如果需要），而不增加算法的复杂性。

2
也有可能用O(1)的时间复杂度完成，但这并不实际；随着n和m的增长，硬件尺寸会迅速增加。 - alx - recommends codidact
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接