Amortized Analysis
L'analyse amortie évalue la borne supérieure du coût total d'une séquence d'opérations répartie sur chaque opération, même si certaines sont occasionnellement coûteuses.
Objectif
Analyser les performances moyennes des structures de données sur des séquences d'opérations, comme l'expansion de tableaux dynamiques.
Mécanisme
Trois méthodes : analyse agrégée (coût total/opérations), méthode comptable (facturer plus les opérations bon marché pour subventionner les coûteuses), méthode potentielle (fonction Φ mesure la complexité de l'état). Insertion de tableau dynamique : O(1) amorti.
Cas d’usage
- Analyse de structures de données
- Garanties de performance
- Conception d'algorithmes