python - 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 仅在可迭代的第一个 t 元素上调用。这是O(t)，但如果t 远小于n 则无关紧要。然后通过 heappushpop 将所有剩余的元素添加到这个“小堆”中，一次一个。每次调用 heappushpop 需要 O(log(t)) 时间。堆的长度始终保持t。最后，堆被排序，这花费 O(t * log(t))，但如果 t 远小于 n，这也无关紧要.

理论的乐趣 ;-)

有相当简单的方法可以在预期的 O(n) 时间内找到第 t 大元素；例如，see here .在最坏的情况下 O(n) 时间有更难的方法。然后，在对输入的另一次传递中，您可以输出 t 元素 >= 第 t 个最大的元素(在重复的情况下会带来繁琐的复杂性)。所以整个工作可以在O(n)时间内完成。

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