Python中collections.Counter（）的时间复杂度是多少？

Question

collection.Counter("bcdefffaa")

返回输出：

Counter({'f': 3, 'a': 2, 'c': 1, 'b': 1, 'e': 1, 'd': 1})

由于结果是按降序排序的值，这是否意味着构建计数器的成本是O(nlogn)，而不是O(n)？

另外，Java中collections.Counter的等价物是什么？

Answer 1

正如source code所示，Counter只是dict的一个子类，构造它是O（n），因为它必须遍历输入，但是对单个元素的操作仍然是O（1）。

还需要注意的是，它并没有在内部保持一个顺序，而只是按照__repr__方法中最常见的输出排序。

Answer 2

显然，这取决于实现，但重要的因素是需要接触原始列表的每个元素，这意味着O（n）是一个下限，需要将元素插入dict和/或更新dict。 输出中元素的显示与构建计数器的成本无关。