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

collection.Counter("bcdefffaa")

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

因为结果是在值下降的排序顺序，这意味着建立反的代价为O（nlogn），而不是为O（n）？

此外，什么是Java中的collections.Counter的相同呢？

它不会**先排序字符串。这只是字典查找。所以最糟糕的时间复杂度是* O（n^2）*，但这是非常罕见的。通常它是* O（n）*。 –

对于Java请参阅：http://stackoverflow.com/documentation/java/88/streams/909/creating-a-frequency-map –

随着source code显示，计数器只是一个字典的子类。构造它是O（n），因为它必须遍历输入，但是对单个元素的操作仍然是O（1）。

还要注意从源头，它不保持一个订单内，而是简单地通过排序上最常见的输出，在__repr__方法。

2017-02-25 21:49:28

依赖于实现，很明显，但重要的因素是触摸原始列表，这意味着为O（n）中的每个元素，需要的是一个下界，并且将元素插入一个字典的需要和/或更新字典。输出中元素的显示与构建计数器的成本无关。

2017-02-25 21:45:29

回答