L'analisi ammortizzata dà il costo medio di una singola operazione. Il costo medio significa che anche se una singola operazione può essere costosa, tuttavia quando si fa una sequenza di tali operazioni, il costo per operazione (costo totale / numero totale di operazioni) diventa piccolo. Questo costo medio è noto come costo ammortizzato e questo tipo di analisi dei costi è noto come analisi ammortizzata.
Ex - Ecco l'esempio molto tradizionale di incremento di un contatore binario.
Supponiamo di avere un numero b bit binario (0000 1111 i.e 15 in decimale)
Ora supponiamo di aggiungere 1 al numero (0001 0000 cioè 16 in decimale).
Ora considerando la singola operazione di cui sopra solo, il costo di eseguire una tale operazione è O(b) dove b è il numero di bit nel numero.
Ora veniamo all'analisi ammortizzata -
Supponiamo di avere il numero 0000 0000 , e di eseguire una sequenza di N operazioni di 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 somma può essere fatta sommando fino a [math]infty [/math], che risulta essere 2*N, poiché il numero di operazioni di incremento sono N quindi dopo aver diviso per N, il costo medio di una singola operazione risulta essere O(1).