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

元素上调用 Heapify。 这是

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)

记忆。 Python 不使用它们。 实际实现的一个优点是，最坏情况下的“额外”内存负担是

O(n)

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

Answer 2

O(t)

Heapq 将为前 t 个元素构建堆，然后它将通过从堆中压入和弹出元素（维护堆中的 t 个元素）来迭代剩余元素。

将完成前 t 个元素的堆构建

O(nlog(t))
1. 对于压入和弹出，剩余的元素将在
tlog(t)
2. 总体时间复杂度为
(n-t)log(t)

Answer 3

n

 + t⋅log n)，因为 heapify 需要 O(n)，并且对于每个最大或最小元素需要 O(log n)。因此，对于 t 最大/最小，需要 t⋅log n。因此，时间复杂度将为 O(n + t⋅log n)。

Answer 4

heapq源码中的注释

： nlog(t)