Complexité en moyenne et complexité typique
Parler de complexité moyenne nécessite d’avoir une distribution probabiliste sur les entrées de l’algorithme. Il s’agit alors de l’espérance du nombre d’opérations nécessaires pour que l’algorithme s’exécute sur une entrée de taille donnée.
Parfois il est plus intéressant de regarder la complexité typique, c’est-à-dire la complexité correspondant à un cas très fréquent décrit par la mesure de probabilité. Imaginons un cas extrême où un algorithme est très performant (linéaire) sur tous les cas sauf un, où sa complexité est astronomique. Sa complexité moyenne risque d’être influencée par ce cas problématique, alors que sa complexité typique restera linéaire.
Estimer la complexité en moyenne
Pour estimer la complexité en moyenne d’un algorithme, il suffit de mesurer le nombre d’opérations élémentaires qu’il décrit en générant des entrées selon la mesure de probabilité voulue.
Ces données statistiques peuvent être riches de sens. Leur moyenne donnera la complexité en moyenne, tandis que l’écart type sera informatif sur le risque encouru à utiliser cet algorithme dans une application temps réel.