algorithm - 给定 10 亿个数字，我们需要找到最大的 100 万个数字

Question

我一直被困在一个问题上。

给定 10 亿个数字，我们需要找到最大的 100 万个数字。一种方法是对数字进行排序，然后从中取出 O(n log n) 中的前一百万个数字。提出一个具有预期 O(n) 时间复杂度的算法。

是堆排序可以通过 O(n) 复杂度做到这一点吗？

标签： algorithmsortingheap

Answer 1

您在此处尝试解决的问题的一般版本似乎如下：

给定 n 个数字，在（可能预期的）时间 O(n) 内报告其中最大的 k 个。

如果您只需要查找前 k 个元素并且排序无关紧要，那么可以使用基于使用快速选择算法的巧妙 O(n) 时间算法来解决此问题。作为复习，选择算法将数组 A 和数字 m 作为输入，然后对数组 A 重新排序，使 m 个最小的元素位于前 m 个槽中，其余元素占据较大的槽。快速选择算法在（预期的）时间 O(m) 内完成此操作，并且在实践中很快；中位数算法在最坏情况下的 O(m) 时间内执行此操作，但在实践中速度较慢。虽然这些算法通常是根据查找最小的k 个元素来构建的，但它们在查找最大的k 个元素时同样有效。

使用这个算法作为子程序，下面是我们如何在时间和空间 O(m) 中找到前 k 个元素的方法：

Initialize a buffer of 2k elements.
Copy the first k elements of the array into the buffer.

While there are elements remaining in the array:
    Copy the next k of them into the buffer.
    Use a selection algorithm to place the k largest elements
      of the buffer in the first k slots of the buffer.
    Discard the remaining elements of the buffer.

Return the contents of the buffer.

要了解为什么会这样，请注意，在循环的每次迭代之后，我们保持缓冲区保存迄今为止已经看到的最大元素的不变量（尽管不一定按排序顺序）。因此，该算法将识别输入的前 k 个元素并以某种顺序返回它们。

就时间复杂度而言 - 创建缓冲区需要 O(k) 次工作，并且在循环的所有迭代中，我们会进行 O(n) 次工作，将元素复制到缓冲区中。每次调用选择算法都需要（预期的）时间 O(k)，并且有 O(n / k) 次调用算法的净运行时间为 O(n + k)。在 k < n 的假设下，这给出了 O(n) 的总体运行时间，只需要 O(k) 的总空间。