Analyse amortie

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[2]. 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 ».

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.

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.

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[3].

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[4] - [5]. Elle a été rendue populaire en analysant avec succès la structure de donnée Union-Find.

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

• 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