¿La complejidad del tiempo de las operaciones del conjunto python?

Question

¿Cuál es la complejidad de tiempo de cada una de las operaciones de conjunto de python en la notación Big O?

Estoy usando Python's set type para una operación en una gran cantidad de artículos. Quiero saber cómo el rendimiento de cada operación se verá afectado por el tamaño del conjunto. Por ejemplo, add, y la prueba de la membresía:

myset = set() 
myset.add('foo') 
'foo' in myset 

googlear alrededor no ha aparecido ningún recurso, pero parece razonable que la complejidad de ejecución conjunto de Python habría sido considerado cuidadosamente.

Si existe, un enlace a algo como this sería genial. Si no hay nada como esto por ahí, entonces quizás podamos resolverlo?

Marcas extra para encontrar la complejidad de tiempo de todas las operaciones de ajuste.

Answer 1

La operación in debe ser independiente del tamaño del contenedor, es decir. O (1) - dada una función hash óptima. Esto debería ser casi true para cadenas de Python. Las cadenas hash siempre son críticas, Python debería ser inteligente allí y por lo tanto, puede esperar resultados casi óptimos.

Answer 2

Según Python wiki: Time complexity, conjunto se implementa como hash table. 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 enfrentará colisiones y O (n).

P.S. por alguna razón, reclaman O (n) para la operación de eliminación que se parece a un tipo incorrecto.

P.P.S. Esto es cierto para CPython, pypy es un different story.