Python集合计数器：most_common复杂度

Python集合计数器：most_common复杂度

从collections.py的源代码中，我们看到，如果不指定返回的元素数，则

most_common

返回计数的排序列表。这是一种

O(nlog n)

算法。

如果使用

most_common

返回

k >1

元素，则使用

heapq.nlargest

。这是一个

O(k)+ O((n - k) log k) + O(k logk)

算法，对于一个很小的常量非常有用

k

，因为它本质上是线性的。这一

O(k)

部分来自对初始

k

计数进行堆放，第二部分来自

n -k

对

heappushpop

方法的调用，第三部分来自对

k

元素的最终堆进行排序。既然

k <= n

我们可以得出结论，复杂度是：

O（n log k）

如果

k = 1

这样的话，很容易表明复杂度是：

上）