Complexité en moyenne des algorithmes

La complexité en moyenne d'un algorithme est la quantité d'une ressource donnée, typiquement le temps, utilisée par l'algorithme lors de son exécution pour traiter une entrée tirée selon une distribution donnée. Il s'agit par conséquent d'une moyenne de la complexité, pondérée entre les différentes entrées possibles selon la distribution choisie. Le plus souvent, on ne précise pas la distribution et on utilise implicitement une distribution uniforme (i.e. une loi uniforme discrète dans le cas discret), c'est-à-dire que toutes les entrées sont considérées comme équiprobables.

C'est une mesure importante pour l'analyse de la complexité des algorithmes, et elle s'oppose à la complexité dans le pire des cas qui considère la complexité maximale de l'algorithme sur toutes les entrées possibles.

Utilité

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.

Choix de la distribution

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 $T(n)=O(n\log n)$, mais dont la complexité dans le pire des cas est $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, définie en fonction de la complexité de Kolmogorov $K$ par $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.

Exemple du tri

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.

Références et bibliographie

Bibliographie

• Andrej Bogdanov et Luca Trevisan, « Average-Case Complexity », Foundations and Trends® in Theoretical Computer Science, vol. 2, n^o 1,‎ 2006, p. 1-106 (lire en ligne)
• Jean-Paul Delahaye, Complexités : Aux limites des mathématiques et de l'informatique, Belin, 2006, « 11 »
• Jean-Paul Delahaye, « La complexité mesurée… : Aux limites des mathématiques et de l'informatique », Pour la science,‎ décembre 2003 (lire en ligne)
• (en) Ming Li et Paul Vitanyi, « Average-case complexity under the universal distribution equals worst-case complexity », Information Processing Letters, vol. 42,,‎ 25 mai 1992, p. 145–149 (lire en ligne)

Articles connexes

• Théorie de la complexité (informatique théorique)
• Analyse de la complexité des algorithmes
• Analyse lisse d'algorithme
• Complexité en temps
• Complexité dans le pire des cas