Analyse amortie

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 la plupart des cas, 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 souvent lié à une structure de données, elle consiste alors, après avoir déterminé les opérations de base, à évaluer le coût cumulé d'une suite d'opérations.

Différences avec l'analyse en moyenne[modifier | modifier le code]

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 : les tableaux dynamiques[modifier | modifier le code]

Dans cet exemple on stocke des vecteurs un tableau dont la taille n'est pas fixée une fois pour toute, mais peut augmenter quand c'est nécessaire. On commence avec un tableau vide ou à une case. Ensuite, pour ajouter un élément :

  • ou bien il reste une case vide et l'on utilise cette case
  • ou bien le tableau est plein et l'on en crée un nouveau dont la taille est augmentée de N cases, dans lesquelles on recopie les anciennes valeurs en y ajoutant la nouvelle.

L'insertion en fin de vecteur se fait alors en temps constant tant que le tableau n'est pas plein, ce qui est vrai le plus souvent, puisqu'il suffit d'écrire le nouvel élément et d'augmenter le compteur de taille du vecteur. En revanche quand le tableau est plein, ce qui est vrai plus rarement, il faut en allouer un autre et recopier tous les éléments ; la complexité est donc alors en O(n), où n est la taille du tableau courant.

En choisissant de façon adéquate le coefficient d'accroissement N du tableau, on peut s'assurer que le coût de l'insertion en fin de vecteur reste globalement marginal, c'est-à-dire en O(1) en moyenne amortie. Une bonne tactique peut consister à doubler la taille du tableau à chaque défaut[1].

Notes et références[modifier | modifier le code]

  1. Voir le paragraphe expansion géométrique et coût amorti de l'article en anglais Dynamic array.

Bibliographie[modifier | modifier le code]