Amortized Complexity

Complejidad Amortizada

La complejidad amortizada mide el costo promedio por operación en una secuencia larga de operaciones, cuando algunas operaciones son ocasionalmente caras.

No analiza una operación aislada sino que analiza el costo total repartido entre muchas operaciones.

Amortizacion en estructuras dinámicas

Normalmente, las estructuras de datos dinámicas como los arrays dinámicos o las tablas hash tienen una complejidad amortizada de O(1) para inserciones, porque aunque ocasionalmente necesiten redimensionar (lo que es O(n)), la mayoría de las inserciones son O(1) resultando en procesos sencillos y baratos para el sistem.

En resumen:

Operaciones baratas repetidas
Cuando se alcanza un límite → reestructuración costosa
Luego muchas operaciones baratas otra vez

Ese costo grande no ocurre frecuentemente por lo que se “amortiza” entre las operaciones baratas.

Como calcular la complejidad amortizada

Para calcular la complejidad amortizada, se pueden usar diferentes métodos, especialmente tenemos tres comúnes.

Cómo se analiza formalmente

Aggregate Method

Sumás el costo total de n operaciones y dividís por n.

Fórmula:

Costo Amortizado = Costo Total de n operaciones / n

Ejemplo Práctico: Dynamic Array (Array Dinámico)

Imagina un array dinámico que crece cuando se llena. Veamos cómo funciona:

Array inicial: [_] (capacidad = 1)
Insertar 1: [1] → O(1)
Insertar 2: [1, _, _] (se redimensiona a 2, luego a 4) → O(n) porque copia elementos
Insertar 3: [1, 2, 3, _] → O(1)
Insertar 4: [1, 2, 3, 4] → O(1)
Insertar 5: [1, 2, 3, 4, _, _, _, _] (se redimensiona a 8) → O(n)
...

Cálculo del Aggregate Method:

Si insertamos 8 elementos:

Inserciones normales (baratas): 1 + 1 + 1 + 1 + 1 + 1 + 1 = 7 operaciones → O(1) cada una
Redimensionamiento (caro):
- Cuando pasamos de 1 a 2: copiar 1 elemento
- Cuando pasamos de 2 a 4: copiar 2 elementos
- Cuando pasamos de 4 a 8: copiar 4 elementos

Total de trabajo:

Inserciones baratas: 7 × 1 = 7 unidades de trabajo
Copias durante redimensionamiento: 1 + 2 + 4 = 7 unidades de trabajo
Total: 7 + 7 = 14 unidades de trabajo para 8 operaciones

Costo Amortizado = 14 / 8 = 1.75 ≈ O(1)

¿Qué significa esto?

Aunque ocasionalmente insertamos elementos y necesitamos copiar todo (O(n)), en promedio cada inserción cuesta O(1) porque:

La mayoría de inserciones son baratas (O(1))
Las redimensionalizaciones caras son ocasionales
El costo se “amortiza” entre todas las operaciones

Output esperado:

Redimensionado: 1 → 2 (1 copias)
Redimensionado: 2 → 4 (2 copias)
Redimensionado: 4 → 8 (4 copias)
Redimensionado: 8 → 16 (8 copias)
Insertar 16 elementos en un array dinámico:
Costo amortizado: O(1) por inserción

Por qué es importante entender esto:

En Big-O notation, decimos que insertar en un dynamic array es O(1) amortizado, no O(n). Esto es diferente de O(1) garantizado (como acceder a un índice), pero es lo suficientemente bueno para la mayoría de aplicaciones reales.

Accounting Method

Asignás “créditos” a operaciones baratas para pagar futuras operaciones caras.

La idea es simple:

Cada operación barata (O(1)) recibe 2 créditos
1 crédito se gasta en la operación misma
1 crédito se guarda para el futuro
Cuando ocurre una operación cara (redimensión), usamos los créditos guardados

Ejemplo: Dynamic Array

Imagina que estamos insertando elementos en un array dinámico:

Operación	Créditos recibidos	Créditos gastados	Créditos acumulados
Insert 1	+2	-1 (operación)	1
Insert 2	+2	-1 (operación) -2 (copiar 1 elem al redimensionar)	0
Insert 3	+2	-1 (operación)	1
Insert 4	+2	-1 (operación) -2 (copiar 2 elem al redimensionar)	0
Insert 5	+2	-1 (operación)	1
Insert 6	+2	-1 (operación)	2
Insert 7	+2	-1 (operación)	3
Insert 8	+2	-1 (operación) -4 (copiar 4 elem al redimensionar)	0

¿Por qué funciona?

Los créditos nunca se agotan (nunca llegan a negativo). Esto demuestra que:

Las operaciones baratas siempre “pagan” las caras
En promedio, cada operación cuesta O(1)
Es como si cada operación dejara dinero ahorrado para pagar la redimensión futura

Conclusión:

El Accounting Method es intuitivo: piensa en los créditos como “deuda futura”. Cada operación barata se adelanta y paga por las operaciones caras que vendrán después.

Contraste: ¿Qué pasaría si NO fuera eficiente?

Escenario ineficiente: Array que se redimensiona sumando +1 en lugar de duplicarse

Imagina un array que en lugar de duplicar su capacidad (x2), solo suma 1 elemento:

Operación	Créditos recibidos	Créditos gastados	Créditos acumulados
Insert 1	+2	-1 (operación)	1
Insert 2	+2	-1 (operación) -1 (copiar 1 elem)	1
Insert 3	+2	-1 (operación) -2 (copiar 2 elem)	0
Insert 4	+2	-1 (operación) -3 (copiar 3 elem)	-2 ❌
Insert 5	+2	-1 (operación) -4 (copiar 4 elem)	-7 ❌
Insert 6	+2	-1 (operación) -5 (copiar 5 elem)	-14 ❌

¿Qué ves?

Los créditos se agotan y se vuelven negativos. Esto significa:

No tienes suficientes créditos para pagar las operaciones caras
Las operaciones baratas NO pueden financiar las redimensionalizaciones
El costo promedio es más alto que O(1)
De hecho, sería O(n) porque cada inserción copia muchos elementos

Conclusión:

El hecho de que los créditos nunca se agoten en el primer ejemplo (duplicar) prueba que es eficiente. El hecho de que se agoten en este segundo ejemplo (sumar +1) prueba que es ineficiente.

Por eso los dynamic arrays usan duplicación (x2), no suma (+1). ¡El Accounting Method te lo muestra claramente!

Potential Method

Usás una función matemática que mide “energía acumulada” en la estructura.

La idea es simple:

La estructura tiene una “energía potencial” que aumenta con operaciones baratas
Las operaciones caras consumen esa energía
Si la energía nunca es negativa, entonces el costo amortizado es O(1)

Ejemplo: Dynamic Array

Define una función potencial:

Φ(estructura) = 2 × (cantidad de elementos) - capacidad

Esto mide cuánto “espacio libre” tienes en el array.

Operación	Tamaño	Capacidad	Φ actual	Cambio en Φ	Costo real	Costo amortizado
Insert 1	1	1	2(1) - 1 = 1	+1	1	1 + 1 = 2
Insert 2	2	4	2(2) - 4 = 0	-1	2 (copia 1)	2 + (-1) = 1
Insert 3	3	4	2(3) - 4 = 2	+2	1	1 + 2 = 3
Insert 4	4	4	2(4) - 4 = 4	+2	1	1 + 2 = 3
Insert 5	5	8	2(5) - 8 = 2	-2	4 (copia 4)	4 + (-2) = 2

¿Cómo interpretar esto?

Φ actual: La “energía” que tiene la estructura en ese momento
Cambio en Φ: Si sube, acumulas energía; si baja, la gastas
Costo amortizado = Costo real + Cambio en Φ

¿Por qué funciona?

Sumamos todos los costos amortizados:

2 + 1 + 3 + 3 + 2 = 11 para 5 operaciones
Costo promedio = 11 / 5 ≈ O(1) amortizado

La clave: El potencial nunca se vuelve negativo, lo que significa que siempre tienes “energía” suficiente para pagar las operaciones caras.

¿Cuál es la diferencia entre Accounting y Potential?

Aunque ambos métodos llegan a la misma conclusión, la forma en que lo hacen es diferente:

Accounting Method

Forma de pensar: “Billetera” con dinero (créditos)

¿Cuánto dinero tengo ahora? → Dinero actual
¿Cuánto gano? → +2 créditos por operación
¿Cuánto gasto? → -1 (operación) y -X (redimensión)
¿Me quedo en rojo? → Si no, es eficiente

Es proactivo: asignas créditos ANTES de gastarlos.

Potential Method

Forma de pensar: “Energía acumulada” en la estructura

¿Cuánta energía tiene la estructura? → Φ(estructura)
¿Cambió la energía? → ΔΦ (cambio)
¿Costo amortizado? → Costo real + ΔΦ
¿La energía nunca es negativa? → Si no, es eficiente

Es analítico: mides la energía de la estructura misma, no créditos externos.

Ejemplo Comparado: Insert 2

Accounting Method:

Recibo: +2 créditos
Gasto: -1 (inserción) -1 (copia de 1 elemento)
Saldo: 0 créditos

Potential Method:

Antes: Φ = 2(1) - 1 = 1
Después: Φ = 2(2) - 4 = 0
Cambio: ΔΦ = 0 - 1 = -1
Costo amortizado: 2 (copia) + (-1) = 1

La gran diferencia

Aspecto	Accounting	Potential
¿Qué mides?	Créditos (dinero externo)	Energía de la estructura
Fórmula	Créditos restantes	Costo real + Cambio de Φ
Mentalmente	”¿Tengo dinero?"	"¿Cuánta energía tiene?”
Uso	Explicaciones intuitivas	Demostraciones matemáticas rigurosas

La conclusión es la misma, pero:

Accounting es como contar dinero en tu billetera
Potential es como medir la energía de un resorte comprimido

Ambos te dicen si algo es eficiente, pero con diferentes “metáforas”.

Comparación de los tres métodos

Método	Cómo funciona	Mejor para
Aggregate	Suma total / número de operaciones	Análisis simple
Accounting	Créditos: operaciones baratas pagan caras	Intuición clara
Potential	Función matemática de energía acumulada	Pruebas formales

Todos llegan a la misma conclusión: insertar en un dynamic array es O(1) amortizado.