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

正如源代码所示,Counter只是dict的一个子类.构造它是O(n),因为它必须迭代输入,但对单个元素的操作仍然是O(1).

另请注意,该源不会在内部保留订单,而只是在__repr__方法中按输出最常见的顺序进行排序.