heapq.nlargest的时间复杂度是多少？

Question

我当时在看这个pycon演讲，时间是34:30，发言人说，可以在中完成获取t元素列表中最大的元素的n操作O(t + n)。

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

Answer 1

扬声器在这种情况下是错误的。实际费用为O(n * log(t))。仅在t可迭代的第一个元素上调用堆化。就是那个O(t)，但如果t小于，则微不足道n。然后，将所有剩余的元素一次通过添加到此“小堆”中heappushpop。O(log(t))每次调用需要花费时间heappushpop。堆的长度始终保持不变t。最后，对堆进行了排序，这很费钱O(t * log(t))，但是如果堆t大小小于，那么这也是无关紧要的n。

理论上的乐趣;-)

有相当容易的方法可以在预期的O(n)时间内找到第t个最大元素。例如，请参阅此处。在最坏的情况下，有更困难的方法可以做到这一点O(n)。然后，在输入上的另一遍操作中，您可以输出t>
=第t个最大元素（在重复的情况下具有繁琐的复杂性）。因此，整个工作 可以 及时完成O(n)。

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