Analyse et complexité amortie
L'analyse amortie (et la complexité amortie qui en découle) est une technique utilisée pour calculer la complexité lorsque plusieurs exécutions successives d'un même bloc de code va être de complexités différentes.
Par l'exemple lors de l'utilisation de structures complexes où les instructions coûteuses ne sont faites qu'un petit nombre de fois lorsque l'on exécute la méthode plusieurs fois (comme pour les listes par exemple).
Ce n'est pas une complexité en moyenne, c'est un moyen de calculer des complexités (maximum)
Définitions
Si lors de l'exécution d'un algorithme $A$, une opération $O$ (ou une fonction) de celui-ci se répète plusieurs fois et que sa complexité diffère selon les appels, le calcul de la complexité de $A$ va nécessiter une analyse fine de de toutes les exécutions de l'opération $O$ car borner la complexité par le maximum conduit (souvent) à surestimer grandement la complexité réelle.
Définition
L'analyse amortie est regroupe un ensemble des techniques permettant de calculer globalement la complexité maximale $C$ de $m$ exécutions successives d'un algorithme.
La complexité amortie de cet algorithme est alors $\frac{C}{m}$.
Il ne faut pas le confondre avec la complexité en moyenne, c'est bien $m$ fois la complexité maximale que l'on considère lorsque l'on effectue les opération successivement.