values - ¿Por qué es la complejidad temporal del método O.(1) list.append() de python?
append python 3 (3)
Como se ve en la documentación de TimeComplexity , el tipo de list de Python se implementa usando una matriz.
Entonces, si se está utilizando una matriz y hacemos algunos apéndices, eventualmente tendrá que reasignar espacio y copiar toda la información al nuevo espacio.
Después de todo eso, ¿cómo puede ser O (1) el peor de los casos?
Se amortiza O (1), no O (1).
Digamos que el tamaño reservado de la lista es de 8 elementos y se duplica en tamaño cuando se acaba el espacio. Quieres empujar 50 elementos.
Los primeros 8 elementos empujan en O (1). La novena dispara la reasignación y 8 copias, seguidas de un empuje O (1). Los siguientes 7 empujan en O (1). El decimoséptimo desencadena la reasignación y 16 copias, seguidas de un empuje O (1). Los siguientes 15 empujan en O (1). El trigésimo tercer desencadena la reasignación y 32 copias, seguidas de un empuje O (1). Los siguientes 17 empujan en O (1).
Entonces, todos los empujes tienen O (1) complejidad, tuvimos 56 copias en O (1) y 3 reasignaciones en O (n), con n = 8, 16 y 32. Tenga en cuenta que esta es una serie geométrica y asintóticamente es igual a O (n) con n = el tamaño final de la lista. Eso significa que toda la operación de empujar n objetos en la lista es O (n). Si amortizamos eso por elemento, es O (n) / n = O (1).
Si observa la nota al pie de página en el documento que vinculó, puede ver que incluyen una advertencia:
Estas operaciones se basan en la parte "Amortizada" de "Peor Caso Amortizado". Las acciones individuales pueden ser sorprendentemente largas, dependiendo de la historia del contenedor.
Al utilizar el análisis amortizado , incluso si tenemos que realizar operaciones costosas ocasionalmente, podemos obtener un límite inferior en el costo "promedio" de las operaciones cuando las considera como una secuencia, en lugar de individualmente.
Por lo tanto, cualquier operación individual podría ser muy costosa (O (n) u O (n ^ 2) o algo aún más grande), pero como sabemos que estas operaciones son poco frecuentes, garantizamos que se puede realizar una secuencia de operaciones O (n) en A tiempo.
Costo de tiempo de anexar a una lista
Los diseñadores de Python utilizaron una idea muy inteligente para asegurarse de que este tiempo de ejecución en el peor de los casos para adjuntar a una lista ocurra con poca frecuencia. Acabamos de ver que cuando Python se agrega a una lista existente y se queda sin espacio, tiene que solicitar una nueva porción de memoria, donde moverá la lista.
Digamos que la longitud de la lista es n. Pero en lugar de solicitar espacio suficiente para una lista de size n + 1 , Python dispone que haya espacio para que crezca la nueva lista, y solicita espacio para una lista de size 2n . La ubicación general de esta manera puede parecer que desperdicia mucho espacio: Python asigna hasta el twice de memoria que la lista realmente necesita. Pero la ventaja es que si agrega elementos a la lista una y otra vez, la lista se mueve con poca frecuencia.