heapq.nlargest的时间复杂度是什么？

Question

我在观看这个 PyCon 演讲，在 34:30 处，演讲者说获取列表中前 t 个最大元素可以在 O(t+n) 的时间复杂度内完成。

这是怎么做到的呢？我理解创建堆本身就需要 O(n) 的时间复杂度，但是 `nlargest` 的时间复杂度是多少呢？是 O(n+t) 还是 O(t)（实际算法是什么）？

- foo

---

你可能会对源代码感兴趣。 - lvc

如果你想要按排序顺序排列，显然这不可能在线性时间内完成。否则，你可以使用 nlargest 并带上 t=n 来比较排序一个列表并在线性时间内完成。如果你只想要 任意 顺序中的 t 个最大元素，则可以使用 quickselect 在 O(n) 的时间内完成。但是 heapq.nlargest 不使用 quickselect，它使用基于堆的算法以排序的方式给出项目。 - user2357112

总的来说，声称时间复杂度为O(t+n)让我感到有些警惕，因为这其实就是O(n)。虽然技术上并不错误，但这种表达方式有点奇怪。 - Niklas B.

Answer 1

在这种情况下，演讲者是错误的。实际成本为O(n * log(t))。Heapify仅在可迭代对象的前t个元素上调用。那是O(t)，但如果t比n小得多，则不重要。然后，所有剩余的元素都通过heappushpop一个接一个地添加到这个“小堆”中。每次调用heappushpop需要O(log(t))时间。堆的长度始终为t。最后，堆被排序，这需要O(t * log(t))的成本，但如果t比n小得多，则也不重要。

理论上有相当简单的方法可以在预期的O(n)时间内找到第t大的元素；例如，在此处查看。还有更难的方法可以在最坏情况下以O(n)的时间完成。然后，在对输入进行另一遍处理时，您可以输出第t大的t个元素（在存在重复项的情况下会出现繁琐的复杂性）。因此，整个工作可以在O(n)时间内完成。

但是这些方法还需要O(n)的内存。Python不使用它们。实际实现的优点是，最坏情况下的“额外”内存负担为O(t)，当输入是生成大量值的生成器时，这可能非常重要。

- Tim Peters

---

太好了，这很有道理；虽然我真的希望 O(t + n) 是正确的，但我还以为我会学到一些新的堆魔法 :) - foo

刚刚编辑中有一个O(n)的方法-但是不幸的是它与堆无关。 - Tim Peters

有趣的事实是：你确实可以在O(n)时间内对数组进行堆化，并以每次查询O(k)的时间获取结果堆的前k个元素。这非常不平凡，而且heapq模块并没有实现它。（实际应用中可能会有巨大的常数因子，使其变得不可行） - Niklas B.

@NiklasB，请问我在哪里可以读到关于这个“O(k)”算法的资料？即使它很复杂，我也非常感兴趣！ - foo

@foo https://dev59.com/Y33aa4cB1Zd3GeqPjOTJ - Niklas B.

Answer 2

对于堆排序中的t个最大或最小值，时间复杂度为O(nlog(t))

Heapq会为前t个元素构建堆，然后通过从堆中推出和弹出元素（保持堆中t个元素）来迭代剩余元素。

1. 构建前t个元素的堆将花费tlog(t)
2. 推入和弹出剩余元素将花费(n-t)log(t)
3. 总时间复杂度将是nlog(t)

- Manu Manoj

Answer 3

根据 heapq源代码中的注释:

# Algorithm notes for nlargest() and nsmallest()
# ==============================================
#
# Make a single pass over the data while keeping the k most extreme values
# in a heap.  Memory consumption is limited to keeping k values in a list.
#

# Theoretical number of comparisons for k smallest of n random inputs:
#
# Step   Comparisons                  Action
# ----   --------------------------   ---------------------------
#  1     1.66 * k                     heapify the first k-inputs
#  2     n - k                        compare remaining elements to top of heap
#  3     k * (1 + lg2(k)) * ln(n/k)   replace the topmost value on the heap
#  4     k * lg2(k) - (k/2)           final sort of the k most extreme values
#
# Combining and simplifying for a rough estimate gives:
#
#        comparisons = n + k * (log(k, 2) * log(n/k) + log(k, 2) + log(n/k))

- tozCSS

Answer 4

实际上它的时间复杂度是O(n+tlog(n))，因为堆化需要O(n)的时间，而对于每个最大或最小元素都需要O(log(n))的时间。因此，对于t个最大/最小值，它需要tlog(n)的时间。因此，时间复杂度将是O(n+t*log(n))。

- Venkata Sri Harsha