Complexité en moyenne des algorithmes

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Ne doit pas être confondu avec algorithme probabiliste.

La complexité en moyenne d'un algorithme est une approche de la théorie de la complexité des algorithmes qui situe l'efficacité de l'algorithme dans le traitement d'entrées tirées au hasard dans une distribution de probabilité spécifique. Elle s'oppose à la complexité dans le pire cas qui considère la complexité maximale de l'algorithme sur toutes les entrées possibles.

Utilité[modifier | modifier le code]

Il existe trois motivations principales pour étudier la complexité en moyenne. Pour certains problèmes qui sont de complexité très élevée dans le pire cas donc théoriquement infaisable, les entrées qui déclenchent ce comportement se produisent rarement en pratique, de sorte que la complexité en moyenne est une mesure plus précise de la performance de l'algorithme. Deuxièmement, l'analyse de la complexité en moyenne fournit des outils et des techniques pour engendrer des instances difficiles de problèmes qui peuvent être utilisés dans des domaines tels que la cryptographie. Troisièmement, la complexité en moyenne permet de discriminer l'algorithme le plus performant en pratique parmi des algorithmes de complexité dans le pire cas équivalente.

Voir aussi[modifier | modifier le code]