Analyse amortie

L'analyse amortie borne le coût moyen par opération sur une séquence d'opérations dans le pire des cas, montrant que des opérations occasionnellement coûteuses peuvent devenir peu onéreuses lorsque leur coût est réparti sur de nombreuses opérations moins chères.

Definition

L'analyse amortie est une méthode permettant de borner le coût total d'une séquence d'opérations sur une structure de données et de le diviser par le nombre d'opérations, produisant un coût amorti par opération qui est valable dans le pire des cas sur l'ensemble de la séquence même lorsque les opérations individuelles diffèrent considérablement en coût.

Scope

Ce sujet aborde les trois techniques standard de l'analyse amortie — la méthode agrégée, la méthode du banquier (ou comptable) et la méthode du potentiel — et leur application aux structures de données dont les opérations individuelles varient en coût, telles que les tableaux dynamiques, les compteurs binaires, les arbres splay et la structure d'ensembles disjoints (union-find). Il distingue le coût amorti du coût moyen et du coût par opération dans le pire des cas.

Core questions

• En quoi le coût amorti diffère-t-il du coût par opération dans le pire des cas et du coût moyen ?
• Comment la méthode agrégée borne-t-elle le coût total d'une séquence d'opérations ?
• Comment la méthode du banquier attribue-t-elle des crédits pour financer des opérations coûteuses ultérieures ?
• Comment la méthode du potentiel utilise-t-elle une fonction de potentiel pour lisser les coûts ?
• Quelles structures de données reposent sur des garanties amorties plutôt que sur des bornes par opération ?

Key concepts

• coût amorti
• méthode agrégée
• méthode du banquier (ou comptable)
• méthode du potentiel
• fonction de potentiel
• doublement de tableau dynamique
• incrémentation de compteur binaire
• union-find avec compression de chemin

Key theories

Méthode du potentiel

La méthode du potentiel attribue un potentiel non négatif à l'état de la structure de données ; le coût amorti d'une opération est son coût réel plus le changement de potentiel, ainsi, les opérations peu coûteuses accumulent un potentiel qui finance les opérations coûteuses ultérieures.

Méthode du banquier (ou comptable)

La méthode du banquier facture certaines opérations plus que leur coût réel, stockant le surplus sous forme de crédit sur les éléments de la structure de données pour financer les opérations coûteuses futures, garantissant que le crédit ne devient jamais négatif.

Clinical relevance

L'analyse amortie explique pourquoi de nombreuses structures largement utilisées sont efficaces en pratique malgré des opérations occasionnellement coûteuses : les tableaux dynamiques (listes redimensionnables), les tables de hachage avec re-hachage, les structures union-find utilisées dans les algorithmes de connectivité et d'arbre couvrant minimal, et les structures auto-ajustables comme les arbres splay reposent toutes sur des garanties amorties plutôt que sur des garanties par opération.

History

Le terme et le cadre systématique de l'analyse amortie ont été introduits par Robert Tarjan en 1985, s'appuyant sur des arguments ad hoc antérieurs. Cette technique a été essentielle pour l'analyse des structures de données auto-ajustables (arbres splay, tas de Fibonacci) développées par Tarjan et Sleator dans les années 1980.

Key figures

• Robert Tarjan
• Daniel Sleator

Seminal works

• tarjan1985amortized
• cormen2009

Frequently asked questions

Le coût amorti est-il identique au coût moyen ?

Non. Le coût moyen est une espérance sur une distribution de probabilité des entrées et peut être violé par une entrée malchanceuse. Le coût amorti est une garantie dans le pire des cas sur une séquence d'opérations sans aucune hypothèse de hasard : le coût total de toute séquence de ce type est borné, de sorte que la moyenne par opération est toujours valable.

Pourquoi l'ajout à un tableau dynamique est-il O(1) amorti alors que le redimensionnement est O(n) ?

Parce que le tableau double généralement sa capacité, les redimensionnements sont rares par rapport aux ajouts, et le travail total de copie sur une séquence de n ajouts est proportionnel à n. Réparti sur tous les ajouts, cela donne un coût amorti constant même si un seul redimensionnement est linéaire.