Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Complexité en moyenne des algorithmes
Résumé
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.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.