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

Question

我在看this pycon talk, 34:30，演讲者说获取n元素列表中的t最大元素可以在O(t + n)中完成

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

Answer 1

在这种情况下，演讲者是错的。实际成本为O(n * log(t))。Heapify仅在iterable的第一个t元素上调用。这是O(t)，但如果t比n小得多，则这是无关紧要的。然后通过heappushpop将所有剩余元素添加到这个“小堆”，一次添加一个。每次调用heappushpop需要O(log(t))时间。堆的长度始终保持t。最后，对堆进行排序，这将花费O(t * log(t))，但是如果t比n小得多，这也不重要

理论的乐趣；-）

有相当简单的方法可以在预期的O(n)时间内找到第t大元素；例如，see here。在最坏的情况下{}有更难的方法。然后，在输入的另一个过程中，您可以输出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)

Answer 3

它实际上是O（n+tlog（n）），因为heapify取O（n），对于最大或最小的元素，取O（log（n））。因此，对于t最大/最小值，需要tlog（n）。因此，时间复杂度将为O（n+t*log（n））