Analyse amortie

En informatique, l'analyse amortie est une méthode d'évaluation de la complexité temporelle des opérations sur une structure de données. Cette analyse résulte en une classification des algorithmes et conduit à une théorie spécifique de la complexité des algorithmes que l'on appelle complexité amortie.

L'analyse amortie consiste essentiellement à majorer le coût cumulé d'une suite d'opérations pour attribuer à chaque opération la moyenne de cette majoration, en prenant en compte le fait que les cas chers surviennent rarement et isolément et compensent les cas bon marché. Pour être utilisable, cette analyse suppose que l'on est capable de borner la fréquence des cas les plus coûteux. L'analyse amortie se place dans le cas le plus défavorable et garantit la performance moyenne de chaque opération dans ce cas. À partir de l'analyse amortie on peut concevoir des structures de données efficaces.

Définition

L'analyse amortie étudie la complexité (temporelle) d'une suite d'opérations effectuées sur une même structure de données. Elle répartit le surcoût de certaines opérations dispendieuses sur toutes les opérations en prenant en compte le fait que la plupart des opérations sont économes. Elle attribue à chaque opération d'une séquence un coût amorti qui est la moyenne arithmétique du coût total sur l'ensemble de ces opérations. Compte tenu des compensations entre opérations (les opérations bon marché en temps contrebalançant les opérations coûteuses), ce temps est, en général, nettement meilleur que celui que donnerait une analyse dans le pire cas.

En répartissant les coûts élevés de certaines opérations sur toutes les opérations, elle escompte qu'un coût moyen raisonnable sera associé à chaque opération. La répartition du coût sur une séquence d'opération ressemble à un amortissement en comptabilité. Le résultat de cette analyse est une majoration de la performance moyenne de chaque opération.

Cette analyse est utilisée avec profit quand on étudie une structure de données qui implique des coûts importants lors d'opérations peu fréquentes comme des rééquilibrages ou des améliorations de son état interne. L'analyse amortie peut alors être utilisée pour montrer que le coût moyen d'une opération est faible et ce, même si cette opération est dispendieuse dans une séquence d'exécution. L'intérêt de cette démarche est donc de fournir une majoration de la complexité tout en donnant le poids qui leur revient (c'est-à-dire comparable aux autres) aux opérations les plus coûteuses d'une suite d'opérations. En gros, les opérations coûteuses le sont parce qu'elles réarrangent, une fois de temps en temps la structure de données, ce dont profitent toutes les autres opérations et l'analyse ne devraient pas les « pénaliser ».

Mise en œuvre

La méthode la plus évidente consiste à utiliser un argument direct pour calculer un majorant du temps total requis pour effectuer une série d'opérations. Trois méthodes peuvent être utilisées pour déterminer la complexité amortie d'un algorithme :

• méthode par agrégation
• méthode comptable
• méthode du potentiel

La méthode par agrégation calcule le coût amorti de chaque opération comme une moyenne arithmétique des opérations dans le cas le plus défavorable. Le coût amorti est donc un majorant du coût moyen. Cette méthode affecte le même coût amorti à chaque opération.

La méthode comptable « fait payer » à des opérations simples le coût des opérations complexes qu'elles occasionneront. Le surcoût, de certaines opérations ancillaires d'une suite, est ainsi totalement compensé par celles qui en sont à l'origine.

La méthode du potentiel « fait payer » les coûts à la structure de données et non plus à chaque opération comme dans la méthode comptable. Conceptuellement, elle s'appuie sur un potentiel (un « capital ») qui est libéré au fur et à mesure pour anticiper le surcoût de certaines opérations futures.

Différences avec l'analyse du cas moyen

L'analyse amortie diffère de l'analyse du cas moyen pour les raisons suivantes :

• dans l'analyse du cas moyen, on cherche à exploiter le fait que les cas onéreux sont peu probables en faisant des hypothèses sur la distribution des entrées ou sur les choix aléatoires effectués dans l'algorithme. Dans cette analyse, chaque opération est considérée indépendamment : il n'y a pas de notion d'état mémoire ;
• dans l'analyse amortie, on ne fait pas appel au calcul des probabilités mais on cherche à exploiter le fait que, dans une suite d'opérations partant d'une donnée quelconque, les cas onéreux ne peuvent pas se produire très souvent, ou de manière très rapprochée et que surtout ils profitent aux autres. Cette analyse requiert donc d'identifier les cas les plus défavorables d'une suite d'opérations et de mesurer leur contribution à l'amélioration globale de l'efficacité de la dite suite. Dans l'analyse amortie, les opérations sont envisagées comme parties d'une séquence globale sur une donnée qu'elles modifient : il y a donc une notion d'état mémoire.

Exemple : les tableaux dynamiques

Analyse amortie de l'opération d'adjonction sur un tableau dynamique

L'analyse amortie peut être illustrée par le calcul de la complexité temporelle d'un algorithme d'insertion dans un tableau dynamique. Pour simplifier, nous admettrons que la structure de données est une zone de mémoire contigüe (un tableau) de quelques dizaines de cases sur laquelle la seule opération disponible est l'insertion. La taille de ce tableau peut augmenter si nécessaire. À l'ajout d'un élément, ou bien le tableau admet encore au moins une case vide ou bien il est totalement rempli. Dans le premier cas l'adjonction du nouvel élément est fait en une opération élémentaire de copie. Dans le second cas, il faut d'abord créer un nouveau tableau dont la taille est supérieure à celle du tableau précédent, puis recopier les éléments de l'ancien tableau, puis insérer l'élément à ajouter.

Tant que le tableau n'est pas plein, cas le plus courant, l'adjonction se fait en temps constant, grâce à deux opérations : l'écriture du nouvel élément dans la première case vide et l'incrémentation du compteur de remplissage du tableau.

En revanche quand le tableau est plein, cas rare, il faut allouer un nouveau tableau et en recopier tous les éléments ; la complexité « classique » de cette opération est en O(n), où n est la taille du tableau courant.

L'analyse amortie s'applique de façon naturelle à ce type d'algorithme dans la mesure où le surcoût occasionné par l'accroissement de la taille du tableau survient rarement. Si n est la taille initiale du tableau, amortir la réallocation consiste à répartir équitablement le coût de l'accroissement de taille sur les n premières adjonctions.

En choisissant de façon adéquate le coefficient d'accroissement n du tableau, on peut garantir que le coût de l'insertion dans un tableau plein reste globalement marginal, conduisant à un coût O(1) pour la moyenne amortie. Une bonne tactique consiste à doubler la taille du tableau à chaque défaut.

Historique

L'une des premières utilisations de l'analyse amortie a été faite par Robert Tarjan pour une variante de la recherche dans un arbre binaire. Elle a été rendue populaire en analysant avec succès la structure de donnée Union-Find.

Voir aussi

• Analyse lisse d'algorithme
• Complexité en moyenne des algorithmes

Bibliographie

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition]. Chapitre 17.
• Robert Endre Tarjan, « Amortized computational complexity », SIAM Journal on Algebraic Discrete Methods, SIAM, vol. 6, n^o 2,‎ 1985, p. 306-318