Complexité en moyenne des algorithmes

Différentes raisons peuvent justifier l'étude de la complexité en moyenne d'un algorithme. Certains problèmes ont une complexité dans le pire des cas très élevée, mais les entrées qui correspondent à ces cas ne se produisent que très rarement en pratique, de sorte que la complexité en moyenne est une mesure plus utile de la performance de l'algorithme. Elle est par conséquent utilisée pour comparer la performance de différents algorithmes entre eux, notamment lorsque ceux-ci ont la même complexité dans le pire des cas, ou lorsque l'on sait qu'il n'est pas nécessaire de considérer le pire des cas car on dispose d'informations supplémentaires sur les entrées qui seront à traiter en pratique.

L'analyse de la complexité en moyenne fournit également des outils et des techniques pour engendrer des instances difficiles de problèmes, qui peuvent par exemple être utilisés dans des domaines tels que la cryptographie.

Le plus souvent, la complexité en moyenne est calculée en considérant que toutes les entrées possibles sont équiprobables. Cela rend le calcul plus facile à réaliser, mais ce n'est pas nécessairement ce qui se passe en pratique.

Parfois, les cas les plus défavorables se produisent avec une probabilité plus forte que d'autres entrées. C'est par exemple souvent le cas de l'algorithme de tri rapide, dont la complexité en moyenne est ${\displaystyle T(n)=O(n\log n)}$, mais dont la complexité dans le pire des cas est ${\displaystyle T(n)=O(n^{2})}$ et est atteinte pour des entrées déjà triées. Une manière d'approcher la probabilité « réelle » des différentes entrées possibles est d'utiliser la mesure de Levin[1]^,[2], définie en fonction de la complexité de Kolmogorov ${\displaystyle K}$ par ${\displaystyle m:s\rightarrow 2^{-K(s)}}$. M. Li et P. Vitanyi ont ainsi montré que la complexité en moyenne du tri rapide pondérée par la mesure de Levin était similaire à la complexité dans le pire des cas[3]^,[4].

Pour les algorithmes de tri, la complexité en moyenne sur la distribution uniforme a été très étudiée. Certains tris comme le tri rapide ou le tri à peigne ont une complexité optimale en moyenne mais pas dans le pire cas. D'autres sont optimaux selon les deux mesures, comme le tri fusion, d'autres encore ne sont optimaux pour aucune des deux mesures, c'est par exemple le cas du tri par insertion.