Si insertar en un dynamic array puede costar O(n) cuando hay que redimensionar, ¿cómo puede ser O(1)?
La respuesta es amortización. Y entenderla cambia cómo pensás sobre el costo de las estructuras de datos dinámicas.
Qué es la complejidad amortizada
La complejidad amortizada mide el costo promedio por operación en una secuencia larga de operaciones. No analiza operaciones aisladas — analiza el costo total distribuido entre todas las operaciones.
La idea es que operaciones ocasionalmente costosas se "pagan" con el crédito acumulado de muchas operaciones baratas anteriores.
El patrón clásico: muchas inserciones baratas → redimensionamiento caro → muchas inserciones baratas → redimensionamiento caro → ...
Aunque el redimensionamiento es O(n), ocurre tan raramente que el costo promedio por inserción sigue siendo O(1).
Método Aggregate
El más intuitivo: sumar el costo total de n operaciones y dividir por n.
Ejemplo: insertar 8 elementos en un dynamic array que empieza con capacidad 1 y se duplica al llenarse.
| Inserción | Costo |
|---|---|
| 1 (+ resize 1→2) | 1 + 1 = 2 |
| 2 (+ resize 2→4) | 1 + 2 = 3 |
| 3 | 1 |
| 4 (+ resize 4→8) | 1 + 4 = 5 |
| 5 | 1 |
| 6 | 1 |
| 7 | 1 |
| 8 | 1 |
Costo total: 15 unidades. Promedio: 15 / 8 = 1.875 ≈ O(1) amortizado.
Método Accounting
Asignás "créditos" a cada operación. Las operaciones baratas ahorran créditos que financian las costosas.
Regla: cada inserción cuesta 2 créditos.
- 1 crédito paga la inserción actual
- 1 crédito se guarda para el futuro redimensionamiento
La condición de validez: los créditos nunca deben volverse negativos. Si en algún momento el balance cae a negativo, la estrategia no funciona y el costo amortizado no es O(1).
Con el array que se duplica (×2), los créditos siempre se mantienen positivos. ¿Por qué? Porque cada redimensionamiento mueve exactamente tantos elementos como los que se insertaron desde el último redimensionamiento, y cada uno de esos elementos ya guardó su crédito.
Contra-ejemplo: si el array creciera de a +1 en lugar de ×2, los créditos eventualmente caerían a negativo. Eso demuestra formalmente que esa estrategia es ineficiente.
Método Potential
El más riguroso matemáticamente. Define una función de potencial Φ que mide la "energía acumulada" en la estructura.
Para un dynamic array: Φ = 2 × elementos − capacidad
La condición de validez: Φ nunca puede ser negativo.
El costo amortizado de cada operación se define como:
Costo amortizado = Costo real + ΔΦ
Donde ΔΦ es el cambio en el potencial después de la operación.
Para una inserción sin resize: costo real = 1, Φ aumenta en 2, costo amortizado = 1 + 2 = 3. Constante, aunque mayor que el costo real — esos 2 de más son el crédito que queda guardado para pagar el resize.
La clave está en la inserción con resize: costo real = n+1 (mover n elementos + insertar), Φ cae de n a 2 —o sea ΔΦ = 2−n—, costo amortizado = (n+1) + (2−n) = 3. Constante.
El método potential tiene la ventaja de prestarse para pruebas formales rigurosas — es la herramienta que usan los papers académicos.
Los tres métodos comparados
| Método | Mecanismo | Cuándo usarlo |
|---|---|---|
| Aggregate | Suma total ÷ n | Análisis simple, panorama general |
| Accounting | Créditos externos | Explicaciones intuitivas, presentaciones |
| Potential | Función de energía interna | Pruebas formales rigurosas |
Los tres llegan a la misma conclusión: insertar en un dynamic array es O(1) amortizado.
Por qué importa en la práctica
Cuando usás ArrayList en Java, vector en C++, o una lista en Python, estás usando estructuras con complejidad amortizada. El costo ocasional del resize está "prepagado" por las inserciones anteriores.
Esto también explica por qué la estrategia de duplicar (×2) es la correcta y no crecer de a uno. Con ×2, el costo amortizado es O(1). Con +1, es O(n). Es una diferencia de órdenes de magnitud disfrazada de un detalle de implementación.