¿Cuál es la complejidad temporal de cada una de las operaciones de conjunto de Python en notación Big O ?
Estoy usando el tipo de conjunto de Python para una operación en una gran cantidad de elementos. Quiero saber cómo el rendimiento de cada operación se verá afectado por el tamaño del conjunto. Por ejemplo, agregue y la prueba de membresía:
myset = set()
myset.add('foo')
'foo' in myset
Buscar en Google no ha generado ningún recurso, pero parece razonable que la complejidad del tiempo para la implementación del conjunto de Python se haya considerado cuidadosamente.
Si existe, un enlace a algo como esto sería genial. Si no hay nada como esto, ¿quizás podamos solucionarlo?
Puntos extra por encontrar la complejidad temporal de todas las operaciones establecidas.
python
data-structures
set
complexity-theory
big-o
Stephen Emslie
fuente
fuente
Respuestas:
Según Python wiki: complejidad de tiempo , el conjunto se implementa como una tabla hash . Por lo tanto, puede esperar buscar / insertar / eliminar en O (1) promedio. A menos que el factor de carga de su tabla hash sea demasiado alto, entonces enfrenta colisiones y O (n).
PD, por alguna razón, reclaman O (n) para la operación de eliminación que parece un error de escritura.
PPS Esto es cierto para CPython, pypy es una historia diferente .
fuente
La operación
indebe ser independiente del tamaño del contenedor, es decir. O (1) : dada una función hash óptima. Esto debería ser casi cierto para las cadenas de Python. El hash de cadenas siempre es fundamental, Python debería ser inteligente allí y, por lo tanto, puede esperar resultados casi óptimos.fuente
Las otras respuestas no hablan de 2 operaciones cruciales en conjuntos: Uniones e intersecciones. En el peor de los casos, la unión tomará O (n + m) mientras que la intersección tomará O (min (x, y)) siempre que no haya muchos elementos en los conjuntos con el mismo hash. Puede encontrar una lista de las complejidades temporales de las operaciones comunes aquí: https://wiki.python.org/moin/TimeComplexity
fuente