Recorrido narrado

Por qué la suma no se dispara

Con la regla de duplicar, cuando el array llega a n valores, los crecimientos copiaron:

1 + 2 + 4 + 8 + … + (la potencia de 2 menor que n)

Con 4 crecimientos se copian 1 + 2 + 4 + 8 = 15, menos que 16, el doble del último término. En general, 1 + 2 + … + 2ᵏ = 2ᵏ⁺¹ − 1, menos que el doble del último término; y como ese término es menor que n, las copias son menos de 2n. A eso se suman las n escrituras de los valores nuevos. En total, menos de 3n operaciones para n inserciones.

En la figura, las 16 primeras inserciones empezando con capacidad 1: cada barra suma la escritura y las copias de esa inserción.

Repartido entre las n inserciones, cada una cuesta menos de 3 operaciones de media. A ese reparto se le llama costo amortizado: O(1) amortizado por inserción.

No dice que cada inserción sea barata. La inserción que provoca un crecimiento copia todo: O(n) en el peor caso. Lo que dice es que, en cualquier secuencia de inserciones, el total está acotado.

función agregar(v, x):    si longitud(v) = capacidad(v):        crecer(v, max(1, 2 × capacidad(v)))    v[longitud(v)] ← x    longitud(v) ← longitud(v) + 1

Su fila en la tabla de costos

El array dinámico completa la fila del array con su regla de crecimiento: