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).

但这些方式也需要O(n)记忆.Python不使用它们.实际实现的优点是最坏情况下的"额外"内存负担O(t),并且当输入是例如产生大量值的发生器时,这可能是非常重要的.

Answer 2

对于 Heapq t 最大或 t 最小，时间复杂度为O(nlog(t))

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

1. 为了构建前 t 个元素的堆，将完成tlog(t)
2. 对于压入和弹出，剩余的元素将在 (n-t)log(t)
3. 总体时间复杂度为nlog(t)