Analyse amortie
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
L'analyse amortie d'un algorithme est une mesure de sa robustesse face aux pires cas. Certains algorithmes ont un bon comportement dans le cas général, et un comportement plus coûteux dans d'autres. Si on peut borner la fréquence de ce dernier cas, alors il est possible de calculer la complexité amortie de l'algorithme.
[modifier] 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 correctement la nouvelle taille du tableau, on peut cependant s'assurer que cette opération reste marginale. Par exemple, si on rajoute N éléments à chaque fois, le tableau sera plein toutes les N opérations. La complexité d'ajout sera donc de ((N-1)*O(1)+O(N))/N, ce qui donne une complexité amortie de O(1).
[modifier] 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.
