heapq.nlargest如何工作？

Question

我在看this pycon talk, 34:30，演讲者说获得t元素列表中的n最大元素可以在O(t + n)中完成。

怎么可能呢？我的理解是创建堆将是O(n)，但是nlargest本身的复杂性是什么，它是O(n + t)还是O(t)（实际的算法是什么）？

Answer 1

在这种情况下，扬声器是错误的。实际成本是O(n * log(t))。Heapify只在iterable的第一个t元素上调用。这是O(t)，但如果t比n小得多，则不重要。然后通过heappushpop将所有剩余的元素添加到这个“小堆”中，一次一个。每次调用O(log(t))都需要heappushpop时间。堆的长度始终保持t。最后，对堆进行排序，这将花费O(t * log(t))，但如果t比n小得多，这也不重要。

理论的乐趣；-）

有相当简单的方法可以在预期的O(n)时间内找到第t个最大的元素；例如，see here。在最坏的情况下，要做到这一点有很多困难的方法。然后，在输入的另一个传递过程中，您可以输出t元素>；=第t个最大的元素（在出现重复的情况下会出现冗长的复杂情况）。所以整个工作可以在O(n)时间内完成。

但这些方法也需要O(n)内存。Python不使用它们。实际实现的一个优点是，最坏情况下的“额外”内存负担是O(t)，当输入是生成大量值的生成器时，这一点非常重要。