¿Qué es el análisis amortizado, utilizando el redimensionamiento de arrays dinámicos como ejemplo?

Question

Accepted Answer

**El análisis amortizado** mide el **costo promedio por operación a lo largo de una secuencia**, incluso cuando las operaciones individuales ocasionalmente cuestan mucho más. Explica por qué el `append` de un array dinámico es "**O(1) amortizado**" a pesar de los redimensionamientos O(n) ocasionales.

## El ejemplo del array dinámico

Cuando un array dinámico se llena, asigna un nuevo array (generalmente **2×**) y copia todos los elementos — un paso O(n). Pero porque la capacidad se **duplica**, las copias costosas se vuelven exponencialmente más raras.

```text
Appending into a doubling array (cap shown):
ops:   1  2  3  4  5  6  7  8  9
cap:   1  2  4  4  8  8  8  8  16
copy:  *  *  *     *           *      <- copies at 1,2,4,8,16...
```

## Las matemáticas

```text
To insert n elements, total copy work =
  1 + 2 + 4 + ... + n  ≈  2n   (geometric series)
Total cost for n inserts = O(n)
Amortized cost per insert = O(n)/n = O(1)
```

```python
arr = []
for i in range(1_000_000):
    arr.append(i)   # almost always O(1); rarely O(n) during a resize
```

| Operación | Peor caso individual | Amortizado |
|---|---|---|
| append (doubling) | O(n) | **O(1)** |

## Por qué duplicar (no +1)

Crecer una **cantidad constante** haría que cada inserción dispare una copia, dando O(n) amortizado. El crecimiento multiplicativo es lo que distribuye el costo.

## Por qué es importante

El análisis amortizado da una imagen justa y realista del rendimiento — sin él, te equivocarías temiendo que cada `append` o inserción en hash-table sea O(n).

También justifica una regla de diseño clave: **crecer la capacidad de forma multiplicativa**, que es la base de los arrays dinámicos, tablas hash y constructores de strings en todas partes.