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. 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.