Analyse amortie
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
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[1]. À partir de l'analyse amortie on peut concevoir des structures de données efficaces.
Définition
[modifier | modifier le code]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 ».
Mise en œuvre
[modifier | modifier le code]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
[modifier | modifier le code]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
[modifier | modifier le code]
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].
Technique de conception d'algorithmes
[modifier | modifier le code]
Historique
[modifier | modifier le code]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.
Notes et références
[modifier | modifier le code]- (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press, , 3e éd. [détail de l’édition]. Chapitre 17, p. 472.
- alors que la complexité dans le pire des cas est une borne pessimiste qui met en exergue des opérations dispendieuses lors d'une exécution particulière qui force l'algorithme à se comporter de façon extrémale.
- Voir le paragraphe expansion géométrique et coût amorti de l'article en anglais Dynamic array.
- Introduction to The design & Analysis of algorithms, Pearson, 2011, Anany Levitin, 3em edition, p. 49
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, [détail de l’édition] Chapitre 17. Notes. p. 419.
Voir aussi
[modifier | modifier le code]Bibliographie
[modifier | modifier le code]- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, [détail de l’édition]. Chapitre 17.
- Robert Endre Tarjan, « Amortized computational complexity », SIAM Journal on Algebraic Discrete Methods, SIAM, vol. 6, no 2, , p. 306-318
