Se llama *análisis amortizado* de complejidad a una forma de medir el costo de ciertas operaciones, en la cual no contamos el tiempo real que toma cada operación particular, sino que medimos el tiempo total que toma realizar $n$ operaciones cualesquiera, y si ese tiempo es $T$, decimos finalmente que cada operación particular tiene una complejidad amortizada de $O\left(\frac{T}{n}\right)$.

Lo interesante es que, como en la inmensa mayoría de los casos nos importa solamente el tiempo total, y no el tiempo que efectivamente tardó una operación en particular, podemos perfectamente realizar todos los cálculos de complejidad suponiendo que las operación tardan siempre el tiempo promedio, y el resultado final obtenido será siempre correcto para el tiempo total.

Varias operaciones de las bibliotecas estándar, como la STL de C++, garantizan sus tiempos de ejecución en forma amortizada, como por ejemplo .push_back() de vector que tiene un tiempo de ejecución $O(1)$ amortizado.

Este es quizás uno de los ejemplos más comunes e importantes de la idea de análisis amortizado.

Supongamos que tenemos una pila, como podría ser por ejemplo stack de la STL de C++. Comenzando con una pila vacía, vamos a realizarle dos tipos de operaciones:

1. Agregar un cierto elemento $x$ a la pila.
2. Sacar una cierta cantidad $k$ de elementos de la pila.

Tanto los $x$ como los $k$ de las operaciones anteriores son arbitrarios, y por ejemplo podemos pensar que los elige un usuario, o se leen de la entrada, sin que tengamos control sobre ellos.

La pregunta que nos hacemos es, ¿Cuál es la complejidad de estas dos operaciones? La operación 1, de agregar, es la más simple, pues consistirá de un único .push() en el stack, que ya sabemos que tiene complejidad $O(1)$ ¹⁾.

Si hacemos un análisis de cuánto tarda la operación de sacar, en el peor caso podrían tener que sacarse muchos números, pues la cantidad que se saca depende del $k$ ingresado. En particular, $k$ podría ser tan grande como todos los elementos que se han agregado en la pila hasta el momento. Por lo tanto en el peor de los casos la operación 2 tiene un costo $O(N)$, siendo $N$ la cantidad de elementos que se agregan en total (es decir, la cantidad de operaciones de tipo 1).

Entonces por ejemplo, si se hacen $1000$ operaciones de tipo $1$, y $1000$ operaciones de tipo $2$, como las operaciones de tipo $2$ pueden costar hasta $1000$ según nuestro análisis previo, el costo total de estas operaciones será como mucho $1000 \cdot 1000$ en el peor de los casos.

Si bien este análisis es correcto, es pesimista: En realidad el costo total será siempre muchísimo menor que $1000 \cdot 1000$. Observemos que, para que el costo total sea tan grande, todas las operaciones de tipo 2 deberían ser caras, es decir, en todas ellas se deberían eliminar todos los números. Pero esto es imposible: Una vez que un número fue eliminado, ya no está en la pila, y no puede “ser eliminado de nuevo”. En otras palabras, cada número que se agrega con una operación tipo 1, puede ser borrado a lo sumo una vez, en una sola operación tipo 2.

Con eso en mente, podemos pensar el costo total de otra manera: En lugar de pensar cuánto cuesta hacer los borrados en una operación particular, pensamos cuántas veces se borra un cierto elemento particular. La observación es entonces que, sin importar en qué operación se borre, cada elemento que se agrega se borra como máximo una única vez, y entonces el costo total de los borrados es proporcional a la cantidad de elementos agregados, es decir, a la cantidad de operaciones de tipo 1.

Si llamamos $N$ al total de operaciones (tanto de tipo 1 como de tipo 2), tenemos entonces resumiendo:

1. Las operaciones de tipo 1 son $O(1)$, y por lo tanto en total ejecutarlas todas tiene un costo $O(N)$
2. Las operaciones de tipo 2 son en total $O(N)$, y lo único “caro” que hacen es borrar elementos, pero en total, el costo de los borrados es $O(N)$. Por lo tanto el costo total de hacer todas las operaciones de este tipo será también $O(N)$.
3. El costo total de ejecutar todas las operaciones es, por los dos anteriores, $O(N)$.
4. Entonces, como $N$ operaciones siempre tienen un costo proporcional a $N$, el costo promedio por operación resulta ser $\frac{N}{N} = 1$. Decimos entonces que ambas operaciones tienen un costo $O(1)$ amortizado: podemos pensar que ambas cuestan $O(1)$, y el costo final que obtendremos al calcular será el correcto.

Supongamos que tenemos que implementar manualmente un contador binario: es decir, vamos a tener que mantener actualizada una lista de dígitos en binario, que representan un número, comenzando desde $0$, e incrementando el número en cada paso.

Si almacenamos el contador binario en un string, podemos inicializarlo con $N$ dígitos cero:

    string contador(N, '0');

Y a continuación, tendremos que implementar la operación de incrementar (sumar $1$) el valor, para completar nuestro contador. Para esto podemos sumar 1 con el algoritmo usual de sumar números: Le sumamos 1 al dígito de las unidades, y si este se pasa de lo permitido, dejamos un 0 y “nos llevamos uno” hacia la izquierda, continuando con la suma.

Esta idea se podría implementar de la siguiente manera:

void incrementar(string &contador)
{
    int N = int(contador.size());
    while (N > 0)
    {
        N--;
        contador[N]++;
        if (contador[N] < '2')
            break;
        else
            contador[N] = '0';
    }
}

Se puede probar el funcionamiento de este contador con por ejemplo el siguiente fragmento:

int main()
{
    int N; cin >> N;
    string contador(N,'0');
    for (int i=0;i<(1<<N)+5;i++)
    {
        cout << contador << endl;
        incrementar(contador);
    }
    return 0;
}

Si se ingresa 3, el resultado por pantalla sería:

000
001
010
011
100
101
110
111
000
001
010
011
100

La pregunta entonces es, ¿Cuánto tiempo toma la ejecución de la función incrementar? En general, la mejor cota que podemos dar para una operación particular es $O(N)$, ya que por ejemplo en el paso que transforma 11111 en 00000, para $N=5$, se deben ir alterando todos los $N$ dígitos.

Sin embargo, veamos que en promedio, el costo de la función es mucho menor.

Para esto, tenemos que pensar exactamente cuántas veces se ejecuta el código interior del while en una llamada particular de la función incrementar. Lo que podemos observar es que esto dependerá del número que se está incrementando:

• Si el número termina en 0, se cambia por 1 y se termina en 1 solo paso.
• Si el número termina en 01, se cambia a 10, y se termina en 2 pasos.
• Si el número termina en 011, se cambia a 100, y se termina en 3 pasos.
• Si el número termina en 0111, se cambia a 1000, y se termina en 4 pasos.
• ...
• Si el número tiene todos 1, se cambia a todos 0, y se ejecutan todos los N pasos posibles.

Entonces, el costo exacto de una llamada a incrementar depende de dónde esté el último cero del número. La mitad de las veces, habrá un 0 al final y se termina en 1 solo paso. La cuarta parte de las veces, el último 0 del número estará a 2 pasos de distancia. La octava parte de las veces, el número terminará con 011 y el cero estará a 3 pasos de distancia. En general, de los $2^N$ números posibles, en $\frac{2^N}{2^i}$ se tardan $i$ pasos en terminar. Por lo tanto, el costo total si procesamos los $2^N$ números con la función incrementar será:

$$T = 2^{N-1} \cdot 1 + 2^{N-2} \cdot 2 + 2^{N-3} \cdot 3 + \cdots + 1 \cdot N$$

Como estamos realizando $n_{ops}=2^N$ operaciones en total, el costo por operación se obtiene dividiendo al anterior por $2^N$, y entonces el costo promedio es:

$$\frac{T}{n_{ops}} = \frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \frac{4}{16} + \frac{5}{32} + \cdots + \frac{N}{2^N} \leq 2$$

[Linkear a alguna explicación de por qué esa suma no se pasa de 2]

Por lo tanto, concluimos que la función incrementar tiene un costo amortizado $O(1)$: si hacemos las $2^N$ llamadas a incrementar necesarias para pasar por todos los valores, el costo total será $2^N \cdot O(1) = O(2^N)$, y no de $2^N \cdot N$, que sería el resultado de hacer un cálculo “pesimista”, como si todas las operaciones fueran caras.

Hemos analizado un contador binario, pero un análisis completamente análogo mostraría que la misma técnica tiene complejidad amortizada $O(1)$ al incrementar un contador ternario, o en base 10, o en cualquier otra base $B \geq 2$.

Algo muy similar a esto ocurre con la función next_permutation, que si se utiliza muchas veces para generar todas las permutaciones de una lista dada, tiene una complejidad amortizada $O(1)$.