Python 中 collections.Counter() 的时间复杂度是多少? [英] What is the time complexity of collections.Counter() in Python?

问题描述

collection.Counter("bcdefffaa")

返回输出:

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

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

Since the result is in descended sorted order of values, does this mean the cost of building the Counter is O(nlogn) and not O(n)?

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

Also, what is the equivalent of the collections.Counter in Java?

推荐答案

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

As the source code shows, Counter is just a subclass of dict. Constructing it is O(n), because it has to iterate over the input, but operations on individual elements remain O(1).

还请注意，它不会在内部保留顺序，而是在 __repr__ 方法中按最常见的输出排序.

Note also from that source that it does not keep an order internally, but simply sorts by most common on output, in the __repr__ method.

这篇关于Python 中 collections.Counter() 的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！