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

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

扬声器在这种情况下是错误的。实际费用为

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)

，当输入是例如生成大量值的生成器时，这可能非常重要。