El Análisis Amortizado da el coste medio de una sola operación. El coste medio significa que aunque una sola operación puede ser cara sin embargo cuando se hace una secuencia de dichas operaciones, el coste por operación (coste total / nº total de operaciones) se hace pequeño. Este coste medio se conoce como coste amortizado y este tipo de análisis de costes se conoce como análisis amortizado.
Ejemplo – Aquí está el ejemplo muy tradicional de Incrementar un contador binario.
Supongamos que tenemos un número binario de b bits (0000 1111 i.e 15 en decimal)
Ahora supongamos que añadimos 1 al número (0001 0000 i.e 16 en decimal).
Ahora considerando la operación única anterior, el coste de realizar una operación de este tipo es O(b) donde b es el número de bits del número.
Ahora llegando al análisis amortizado –
Supongamos que tenemos el número 0000 0000 , y realizamos una secuencia de N operaciones de incremento.
Number – 0000 0000
operation 1 – 0000 0001
operation 2 – 0000 0010
operation 3 – 0000 0011
operation 4 – 0000 0100
operation 5 – 0000 0101
operation 6 – 0000 0110
…… N times.
Now observing closely, the leftmost bit (lsb) alternates for every increment operations, i.e half numbers are odd (lsb 1) and half are even(lsb 0). It is flipped every time a number is incremented.
Similarly for 2nd bit, it is fipped every other time i.e (n/2 times) while incrementing n times.
The similar pattern can be seen in other bits.
Now for a number N , number of bits(b) = log(N).
therefore calculating sum of flips for each bit , the total number of flips done are
[math]sum_{i=0}^{log(N)} frac{1}{2^i}[/math]
La suma se puede hacer sumando hasta [math]infty[/math], que resultan ser 2*N, ya que el número de operaciones de incremento son N por lo que después de dividir por N, el coste medio de una sola operación resulta ser O(1).