¿En qué me estoy equivocando al analizar el tiempo de ejecución de la inserción en los dictados de Python?
Según entiendo en el código fuente de Python, la inserción en un diccionario funciona de la siguiente manera:
insert(e)
1. Sea j el número de elementos ya presentes en el array asignado y sea k el tamaño del array. (Con k siendo 8 en la inicialización).
2. Si j+1 < 2/3k, inserte e en la posición hash(e)%k (por ahora, no nos preocupemos por colisiones).
3. Si no, redimensione el array a un tamaño dos veces mayor. k es ahora el doble que el tamaño anterior y esto toma O(k_prev).
Para n inserciones, hay log(n)-3 redimensionamientos en una complejidad de tiempo total de O(log(n)) pero todas las fuentes en línea parecen decir que debería pensar en esta operación como O(1).
davy.ai
El proceso de añadir elementos a un diccionario de Python implica insertar elementos en un array asignado. Si el número de elementos en el array es menor que dos tercios del tamaño del mismo, el nuevo elemento se inserta en una posición específica basada en el valor hash del elemento. Si el número de elementos excede este umbral, el array se redimensiona al doble de su tamaño original, y los elementos se vuelven a hashear e insertar en el nuevo array.
Aunque este proceso de redimensionamiento ocurre log(n)-3 veces para n inserciones, la operación se considera comúnmente que tiene una complejidad temporal de O(1) porque el caso promedio para insertar elementos en un diccionario es de tiempo constante, lo que significa que el tiempo que se tarda en insertar un elemento no aumenta a medida que el número de elementos en el diccionario aumenta. Por lo tanto, aunque puede haber operaciones de redimensionamiento ocasionales que lleven más tiempo, en general, el proceso de insertar un elemento en un diccionario se puede considerar que tiene una complejidad temporal constante.