L'analyse amortie donne le coût moyen d'une opération unique. Le coût moyen signifie que même si une opération unique peut être coûteuse, cependant lorsque vous effectuez une séquence de telles opérations, le coût par opération (coût total / nombre total d'opérations) devient faible. Ce coût moyen est connu sous le nom de coût amorti et ce type d'analyse de coût est connu sous le nom d'analyse amortie.
Ex - Voici l'exemple très traditionnel de l'incrémentation d'un compteur binaire.
supposons que nous ayons un nombre binaire de b bits (0000 1111 i.e 15 en décimal)
Supposons maintenant que nous ajoutons 1 à ce nombre (0001 0000 soit 16 en décimal).
Supposons maintenant que l'on considère la seule opération ci-dessus, le coût d'exécution d'une telle opération est O(b) où b est le nombre de bits du nombre.
En venant maintenant à l'analyse amortie -
Supposons que nous avons le nombre 0000 0000 , et que nous effectuons une séquence de N opérations d'incrémentation.
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 somme peut être faite en additionnant jusqu'à [math]infty[/math], qui s'avèrent être 2*N, puisque le nombre d'opérations d'incrémentation sont N donc après avoir divisé par N, le coût moyen d'une seule opération s'avère être O(1).