Analyse amortie

En informatique, l'analyse amortie consiste à borner le temps d'exécution moyen d'un algorithme lorsqu'il est répété plusieurs fois de suite. Certains algorithmes ont un bon comportement dans le cas général, et un comportement plus coûteux dans d'autres. L'analyse amortie est utile si on peut borner la fréquence de ce dernier cas.

L'analyse amortie est différente de l'analyse en moyenne :

• dans l'analyse en moyenne, on cherche à exploiter le fait que le pire cas est peu probable en faisant des hypothèses sur la distribution des entrées ou sur les choix aléatoires effectués dans l'algorithme ;
• dans l'analyse amortie, on cherche à exploiter le fait que le pire cas de l'algorithme ne peut pas se produire plusieurs fois consécutivement, ou de manière trop rapprochée, quelle que soit l'entrée.

Exemple

L'insertion en fin de tableau : le coût dans le cas général est en O(1), puisqu'il suffit d'écrire le nouvel élément et d'augmenter le compteur de taille. Mais si le tableau est plein, il faut en allouer un autre et recopier tous les éléments ; la complexité est donc en O(n).

En choisissant de façon adéquate le coefficient d'accroissement du tableau, on peut s'assurer que le coût de cette opération reste globalement marginal.

Par exemple, si on ajoute N éléments à chaque fois que c'est nécessaire, le tableau sera plein toutes les N opérations. La complexité d'ajout sera donc de $\frac{\scriptscriptstyle (N-1)*O(1)+O(N)}{\scriptscriptstyle N}$, ce qui donne une complexité amortie de O(1).

Références

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction à l'algorithmique. MIT Press and McGraw-Hill, 2001. Chapitre 17.