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(\frac{T}{n})$.

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.

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

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)$.