collection.Counter("bcdefffaa")devuelve la salida:
Counter({'f': 3, 'a': 2, 'c': 1, 'b': 1, 'e': 1, 'd': 1}) Dado que el resultado está en orden descendente de valores, ¿significa esto que el costo de construir el Contador es O(nlogn) y no O(n) ?
Además, ¿cuál es el equivalente de las colecciones. Contador en Java?
Como muestra el código fuente , Counter es solo una subclase de dict. Construirlo es O(n), porque tiene que iterar sobre la entrada, pero las operaciones en elementos individuales siguen siendo O(1).
Tenga en cuenta también de esa fuente que no mantiene un orden interno, sino que simplemente ordena por más común en la salida, en el método __repr__ .
Depende de la implementación, obviamente, pero los factores que importan son la necesidad de tocar cada elemento de la lista original, lo que implica que O(n) es un límite inferior, y la necesidad de insertar elementos en un dict y/o actualizar un dict . La visualización de los elementos en la salida no es relevante para el costo de construcción del Mostrador.