这个算法难道不是O(m log n)的时间复杂度吗？

Question

我正在解决一个面试问题，来自 Glassdoor软件工程师。

问题是：

给定100万个数字的列表，如何以有效的方式查找列表中的前n个数字

以下是同一链接中作者提供的解决方案：

1. 创建一个最小堆
2. 取m个元素中的前n个并放入堆中 (O(n))
3. 对于每个剩余的(m-n)个元素，如果它大于堆的最小值，则将其插入堆中并删除最小值。 (最坏情况下 O((m-n)log n) 如果列表已排序。

净结果是您可以在O(n)内存使用和最坏情况下O((m-n)logn)运行时完成此操作。

我同意作者的算法以及作者对此算法的空间复杂度的评估。但我对作者关于插入堆和整体时间的运行时间分析有问题。

对于步骤“取m个元素中的前n个并放入堆中”，这不会在O(nlogn)中运行吗？至少根据我的课堂笔记堆添加，插入将是O(logn)，因为您正在插入n个元素，所以整个步骤的运行时间将为O(nlogn)。

考虑到这一点，整个算法的总运行时间不会是从大O求和中使用的吗？

O(nlogn + (m-n)logn) = O(mlogn)

- committedandroider

---

请注意，在随机分布的列表中，堆中替换的数量非常少，这使得实际时间更接近于O(m)。有关详细信息，请参见http://stackoverflow.com/a/28576512/1980909。 - Adrian Leonhard

Answer 1

使用这种方法来构建堆，是的，但是有一种O(n)的算法可以将数组转换为堆。详见http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap。

话虽如此，对于这个问题，存在一个O(m)时间，O(n)内存的解决方案，例如Guava的Ordering.leastOf。其中一种实现方式为：

• 创建一个缓冲区，大小为2n的数组
• 循环遍历原始数组，将元素添加到缓冲区中
• 每当缓冲区满时，使用O(n)的快速选择算法仅保留缓冲区中最高的n个元素并丢弃其余元素。
• 使用最后一个快速选择算法从缓冲区中提取最高的n个元素

这需要O(m/n)个快速选择，每个选择需要O(n)的时间，总共需要O(m)的时间。

- Louis Wasserman

---

是的，抱歉，我习惯于使用n和k，而不是这里的m和n。 - Louis Wasserman

Answer 2

“对于步骤“取出m个元素中的前n个并放入堆中”，这样做的时间复杂度不是O(nlogn)吗？”

不一定。你可以用O(n)的时间从n个元素中创建一个堆。请参考here了解如何实现。

因此，总时间复杂度为O(n + (m - n)log n) = O((m - n)log n) = O(m log n)。最后一步只有在将n视为常数时才正确，否则应保持为m - n，就像作者所说的那样。

跟进问题：你能用O(m)的时间复杂度解决整个问题吗？

- IVlad