Posterior a consultar especialistas en el tema, programadores de deferentes ramas y profesores hemos dado con la respuesta al problema y la plasmamos en este post.
Solución:
Se amortiza O(1), no O(1).
Digamos que el tamaño reservado de la lista es de 8 elementos y se duplica cuando se agota el espacio. Quiere empujar 50 elementos.
Los primeros 8 elementos empujan en O(1). El noveno desencadena la reasignación y 8 copias, seguidas de un impulso O(1). Los siguientes 7 empujan en O(1). El decimoséptimo desencadena la reasignación y 16 copias, seguidas de un impulso O(1). Los siguientes 15 pulsan en O(1). El trigésimo tercero activa la reasignación y 32 copias, seguidas de un impulso O(1). Los siguientes 17 empujan en O(1).
Entonces, todos los impulsos tienen una complejidad O(1), teníamos 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 a la lista es O(n). Si nosotros amortizar que por elemento, es O(n)/n = O(1).
Si observa la nota al pie en el documento que vinculó, puede ver que incluyen una advertencia:
Estas operaciones se basan en la parte “Amortizada” del “Peor caso amortizado”. Las acciones individuales pueden llevar mucho tiempo, según el historial del contenedor.
Usando 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 mayor, pero como sabemos que estas operaciones son raras, garantizamos que se puede realizar una secuencia de operaciones O(n) en A tiempo.
valoraciones y reseñas
Recuerda dar difusión a este tutorial si lograste el éxito.