Complexité amortie en termes simples ?

Question

Quelqu'un peut-il expliquer la complexité amortie en termes simples ? J'ai eu du mal à trouver une définition précise en ligne et je ne sais pas quel est le rapport avec l'analyse des algorithmes. Toute information utile, même si elle est référencée à l'extérieur, serait très appréciée.

Answer 1

Cela revient en quelque sorte à multiplier la complexité la plus défavorable des différentes branches d'un algorithme par la probabilité d'exécution de cette branche, puis à additionner les résultats. Ainsi, si une branche a très peu de chances d'être exécutée, elle contribue moins à la complexité.