我在看 这个pycon谈话，34：30 并且发言者说得到了 t 列表中最大的元素 n 元素可以完成 O(t + n)。
怎么可能？我的理解是创建堆将是 O(n)，但是复杂性是多少？ nlargest 本身就是这样 O(n + t) 要么 O(t) （什么是实际的算法）？
我在看 这个pycon谈话，34：30 并且发言者说得到了 t 列表中最大的元素 n 元素可以完成 O(t + n)。
怎么可能？我的理解是创建堆将是 O(n)，但是复杂性是多少？ nlargest 本身就是这样 O(n + t) 要么 O(t) （什么是实际的算法）？
在这种情况下，发言者是错误的。实际成本是 O(n * log(t))。仅在第一个时调用Heapify t 可迭代的元素。那是 O(t)但如果是微不足道的话 t 比小得多 n。然后将所有剩余的元素添加到此“小堆”中 heappushpop， 一次一个。这需要 O(log(t)) 每次调用的时间 heappushpop。堆的长度仍然存在 t 始终。在最后，堆被分类，这是成本 O(t * log(t))，但如果这也是微不足道的 t 比小得多 n。
有很简单的方法可以找到预期的最大元素 O(n) 时间;例如， 看这里。在最坏的情况下，有更难的方法 O(n) 时间。然后，在输入的另一个传递中，您可以输出 t 元素> =第t大（在重复的情况下有繁琐的并发症）。整个工作 能够 完成 O(n) 时间。
但这些方式需要 O(n) 记忆也。 Python不使用它们。实际实现的优点是最坏情况下的“额外”内存负担 O(t)当输入是例如产生很多值的发生器时，这可能是非常重要的。