函数的复杂度是多少 most_common由 collections.Counter 提供Python 中的对象？
更具体地说，是 Counter在计数时保留某种排序列表，允许它执行 most_common比 O(n) 更快的操作当n是添加到计数器的(唯一)项目的数量吗？供您引用，我正在处理大量文本数据，试图找到第 n 个最常见的标记。
我查看了official documentation和 TimeComplexity article在 CPython wiki 上，但我找不到答案。
最佳答案
来自collections.py的源代码，我们看到如果我们不指定返回元素的数量，most_common返回计数的排序列表。这是 O(n log n)算法。
如果我们使用 most_common返回 k > 1元素，然后我们使用 heapq.nlargest .这是 O(k) + O((n - k) log k) + O(k log k)算法，非常适合小常数k ，因为它本质上是线性的。 O(k)部分来自堆积初始 k计数，第二部分来自 n - k调用heappushpop方法和第三部分来自对 k 的最终堆进行排序元素。从 k <= n我们可以得出结论，复杂性是:
O(n log k)
如果 k = 1那么很容易证明复杂性是:
O(n)
关于Python collections.Counter : most_common complexity，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29240807/