Arrays y arrays dinámicos
Memoria contigua → acceso aleatorio O(1).
Tamaño fijo → crecer duplicando.
El problema del append
- Queda espacio → escribe, O(1)
- Almacén lleno → asigna uno más grande, copia todo, O(n)
- Crecer de +1 en +1 → redimensiona cada vez, O(n) por append
- Crecer ×2 → los redimensionamientos se vuelven exponencialmente más raros
O(1) amortizado
1+2+4+⋯+n=2n−1=O(n)
El copiado total a lo largo de n appends es lineal →
nO(n)=O(1) por append.
Trace: 63 copias en 64 appends ≈ una cada uno.
Copias por append: el diente de sierra
Picos en 1, 2, 4, 8, 16, 32 — al doble de distancia cada vez.
Míralo llenarse y duplicarse
Costos
- Acceso aleatorio por índice: O(1)
- Append: O(1) amortizado
- Insertar / borrar al inicio o en medio: O(n)
- Amigable con el cache: memoria contigua
Para llevar
Barato al final y por índice, caro en medio.
Eso es el array — y la línea base a la que reacciona toda estructura posterior.