Una tabla hash tiene una complejidad de tiempo esperada para la inserción, eliminación y verificación de membresía que es constante en el número de entradas que se almacenan. El conjunto de Python se basa en una implementación de tabla hash.
Pero esto oculta algunos supuestos que pueden ser violados en la práctica.
La inserción de tiempo constante supone que podemos amortizar el costo de cambiar el tamaño de la tabla hash en muchas inserciones. Por ejemplo, si duplicamos el tamaño de la tabla hash cada vez que necesitamos aumentarla, entonces el costo por inserto es constante, aunque algunos de los insertos pueden ser bastante caros. Entonces, la complejidad de tiempo O (1) en realidad significa O (1) complejidad de tiempo amortizada , mientras que el peor de los casos sigue siendo O (n).
- ¿Cuáles son los beneficios del ordenamiento dinámico y sus desventajas en comparación con otros algoritmos de ordenamiento?
- ¿En qué punto una gran notación O de velocidad de aumento más rápida ignora una notación O grande de velocidad de aumento más lenta?
- ¿Qué puedes hacer con los algoritmos?
- ¿Debo usar kits de herramientas como scikit-learn para comenzar con el aprendizaje automático?
- Cómo escribir un algoritmo
La verificación de membresía de tiempo constante supone que hay un tamaño máximo de clave, pero en realidad la operación “en” puede depender del tamaño de los elementos en el conjunto. Realicé un experimento simple en mi computadora portátil en el que creé un conjunto de 3 elementos de enteros largos de tamaño creciente, y medí el tiempo que tardó en verificar la membresía de un elemento en el conjunto, y uno no en el conjunto:
10e5 bits: 6.7e-7 segundos cuando está presente, 5.9e-7 segundos cuando no está presente
10e6 bits: 5.1e-6 / 5.1e-6
10e7 bits: 5.0e-5 / 5.0e-5
10e8 bits: 5.1e-4 / 5.1e-4
Es decir, un aumento de 10 veces en el tamaño de la clave condujo a un aumento de 10 veces en el tiempo necesario para establecer la membresía.
Un conjunto de elementos [math] n [/ math] debe usar al menos [math] log_2 n [/ math] bits para identificar cada elemento, lo que significa que la búsqueda de membresía es en realidad [math] O (\ log n) [/ math ], porque requiere una comparación. Pero a veces simplemente ignoramos esto o decimos que la verificación de membresía es [matemática] O (k) [/ matemática] donde [matemática] k [/ matemática] es el tamaño de la clave.
Finalmente, la complejidad de tiempo esperada [matemática] O (1) [/ matemática] asume un modelo no contencioso en el que las claves se distribuyen aleatoriamente (o aleatoriamente después del hash), no elegidas por un oponente con conocimiento de la función hash. Consulte Generación de colisiones hash de 64 bits para DOS Python – Robert Grosse – Medio. Python 3.3 activa la aleatorización de hash de forma predeterminada, que intenta combatir esta forma de ataque, y Python 3.4 cambió a una función hash más segura.
