1

这是一个我坚持的家庭作业问题。

我需要对一个 n 元素数组进行排序，以便前 k 个元素是最低的并且按递增顺序排列。对于 k <= n/log(n)，算法应该是 O(n)。

我的解决方案：我想到的一个简单的解决方案是对数组进行 heapify (O(n))。然后删除 k 元素并将堆/数组的起始索引从 0 移动到 1 - 2 - 3（依此类推，一直到 k）。这将是 O(n+k*lg(n)+k*n) = O(kn+k*lg(n))。对于给定的 k 条件，它将是 O(n^2/log(n) + n)。

另一种可能的实现是使用基数排序，这将是 O(n)，但我觉得这不是正确的解决方案，因为我将对整个数组进行排序，而他们只要求对 k 个元素进行排序。

您不必给我答案，只是提示会有所帮助。

4

2 回答 2

1

我喜欢你的堆想法。实际上，我认为它会在您列出的时间范围内起作用，并且您的分析中存在一些小故障。

假设您执行以下操作：在数组中构建一个就地堆，然后将最少 k 个元素出列，将剩余的 n - k 个元素留在数组中的位置。如果您考虑元素将在哪里结束，您应该将数组中的 k 个最小元素按升序存储在数组的后面，而剩余的 n - k 个元素将按堆顺序存储在前面。如果您无法看到这一点，请考虑堆排序的工作原理 - 在 k 个出队之后，最大的 k 个元素在后面按降序排列，其余元素在前面按堆排序。在这里，我们将最小堆换成了最大堆，因此出现了奇怪的排序。因此，如果你在最后反转数组，你应该在前面有 k 个最小元素以升序排列，然后是 n - k 个剩余元素。

这将正确找到k个最小的元素，并且运行时间确定如下：

  • heapify 的成本：O(n)
  • k 出队成本：O(k log n)
  • 反转数组的成本：O(n)
  • 总成本：O(n + k log n)

现在，假设 k ≤ n / log n。然后运行时是

O(n + k log n) = O(n + (n / log n) log n) = O(n)

所以你完成了！该算法工作得很好。另外，它需要 O(1) 辅助空间（堆可以就地构建，并且可以在 O(1) 空间中反转数组）。

不过，你可以做得更好。@timrau 在评论中建议您使用快速选择（或更一般地说，任何线性时间选择算法）。这些算法重新排列数组，以某种顺序将最低 k 个元素放在数组的前 k 个槽中，并将剩余的 n - k 个元素按某种顺序放在最后 n - k 个槽中。这样做需要时间 O(n) 而不管 k （漂亮！）。所以假设你这样做，然后只对前 k 个元素进行排序。这需要时间 O(n + k log k)，渐近优于 O(n + k log n) 时间的基于堆的算法。

在已知的线性时间选择算法中，如果你小心的话，快速选择和中位数算法都可以就地实现，因此这种方法所需的总空间是 O(1)。

于 2015-08-26T20:45:17.687 回答
-1

我突然想到，您可以使用稍微修改的堆选择算法就地执行此操作，即 O(n log k)。尽管与 Quickselect 的 O(n) 复杂度渐近“差”，但当 k 与 n 相比非常小时，堆选择可以胜过 Quickselect。有关详细信息，请参阅理论与实践的结合。但是，如果您要从一百万个列表中选择前 1,000 个项目，那么堆选择几乎肯定会更快。

无论如何，要做到这一点，您从数组中的前 k 个项目构建一个大小为 k 的最大堆（使用标准 BuildHeap 函数）在数组的前面。这需要 O(k)。然后，您像这样处理数组中的其余项目：

for (i = k; i < length; ++i)
{
    if (array[i] < array[0])  // If item is smaller than largest item on heap
    {
        // put large item at the current position
        temp = array[i];
        array[i] = array[0];

        // put new item at the top of heap and sift it down
        array[0] = temp;
        SiftDown(0);
    }
}

这将花费 O(n log k) 时间，但限制因素实际上是您必须在条件内执行多少次代码。只有当一个项目小于堆上已经存在的最大项目时，此步骤才会进行任何处理。最坏的情况是当数组处于反向排序顺序时。否则它会出奇的快。

完成后，最小的 k 个项目位于数组的前面。

然后你必须对它们进行排序，即 O(k log k)。

所以完整的过程是 O(k + n log k + k log k)。同样，当 k 远小于 n 时，这比 Quickselect 快得多。

于 2015-08-26T23:09:11.950 回答