Análisis amortizado

A veces una operación que parece cara, cuando la observas aislada, en realidad sucede muy poco. Si la promediás sobre todas las operaciones que se hicieron, el costo es bajo. Eso se llama análisis amortizado.

El ejemplo canónico: append en un arreglo dinámico (Python list, JS Array, ArrayList en Java).

El problema

Un arreglo dinámico tiene un buffer interno de capacidad fija. Cuando agregas un elemento y el buffer está lleno, hay que pedir un buffer más grande, copiar todos los elementos y liberar el viejo.

Esa copia es O(n). Pero solo pasa cuando se llena. La mayoría de las veces, append es O(1) (solo asignás el elemento en la siguiente posición).

¿Cómo decimos que append es O(1) si a veces es O(n)?

Estrategia de duplicación

El punto: cuando el buffer se llena, el lenguaje no agranda en 1. Agranda al doble.

Si arrancas con capacidad 1 y haces 8 appends, las copias caras pasan en los inserts 1, 2, 4, 8 (cuando se duplica). Los costos son 1, 2, 4, 8 = 15 operaciones de copia. Total de operaciones: 8 inserts + 15 copias = 23. Promedio por insert: 23/8 ≈ 2.88. Es decir, O(1) amortizado.

Para n inserts en general, las copias suman aproximadamente 2n. Total: ~3n operaciones. Promedio por insert: ~3 = O(1).

La definición formal

Una secuencia de m operaciones tiene costo amortizado de O(f(m)) si el costo total de las m operaciones es O(m · f(m)).

Cuando decimos "append es O(1) amortizado", queremos decir: hacer n appends cuesta O(n) en total, aunque alguno individual sea caro.

Otros casos importantes

Hash maps (Python dict, JS Map)

Insertar es O(1) amortizado. Cuando la tabla se llena (por encima de cierto factor de carga), se redimensiona, lo cual cuesta O(n). Pero igual que en arreglos dinámicos, la redimensión se hace al doble, así que el costo total de N inserts es O(N).

Unión por rango en Union-Find

Cada operación de union/find es O(α(n)) amortizado, donde α es la inversa de Ackermann (prácticamente constante para todos los valores prácticos de n). Lo veremos en detalle en grafos.

Eliminación en stacks de monotonic stack

Cada elemento se inserta una vez y se elimina como máximo una vez. Si tienes un loop que en el peor caso hace N pops adentro, el costo total sigue siendo O(N), no O(N²). Lo veremos en monotonic stack.

Cuándo NO sirve el amortizado

El análisis amortizado da costo promedio sobre la secuencia. No da garantía sobre operaciones individuales.

Si tu sistema tiene SLA estricto (cada request tiene que terminar en X ms), no puedes depender de amortizado. Una operación específica puede ser cara aunque el promedio sea bajo. Por ejemplo, un append cuando se duplica el buffer puede tardar mucho más que el resto.

En esos casos hay estructuras alternativas que dan O(log n) peor caso para todas las operaciones (árboles balanceados) en lugar de O(1) amortizado.

Cómo justificarlo en una entrevista

Si tu solución usa una estructura dinámica (list, dict, set), no necesitas disculparte por el costo de redimensionado. Di:

"Append es O(1) amortizado. Aunque algunas operaciones internas son O(n) cuando se redimensiona el buffer, el costo total para n inserts es O(n) porque la duplicación garantiza que las redimensiones son raras y baratas en promedio."

Cualquier entrevistador serio te lo va a aceptar. Si te pide más detalle, puedes explicar la suma 1 + 2 + 4 + ... + n ≈ 2n.