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

回答