Complexité dans le pire des cas
En informatique, la complexité dans le pire des cas, ou complexité dans le cas le plus défavorable, mesure la complexité (par exemple en temps ou en espace) d'un algorithme dans le pire des cas d'exécution possibles. Elle est exprimée comme une fonction de la taille de l'entrée de l'algorithme. Implicitement, on cherche à construire des algorithmes s'exécutant en utilisant le moins de ressources possible (e.g. le plus vite possible), et il s'agit par conséquent d'une borne supérieure des ressources requises par l'algorithme.
Par exemple, la complexité en temps dans le pire des cas correspond au temps d'exécution le plus long que puisse avoir l'algorithme, et permet d'en garantir la terminaison.
La complexité dans le pire des cas permet de comparer l'efficacité de deux algorithmes. Elle s'oppose à la complexité en moyenne.
Exemple
Pour la recherche d'un élément dans une liste, la recherche séquentielle qui consiste à considérer tous les éléments les uns après les autres jusqu'à avoir trouvé la cible (si elle existe), a une complexité dans le pire cas qui est de l'ordre de la taille de la liste : l'élément peut être à la toute fin. Par contre la complexité dans le meilleur des cas est constante : l'élément peut se trouver en début de liste. Et la complexité moyenne (pour une distribution uniforme) est aussi de l'ordre de la taille de la liste.
Le tri rapide avec choix du pivot arbitraire sur une liste de taille a une complexité en sur des permutations aléatoires. Toutefois, si l'entrée est déjà triée, le principe diviser pour régner perd son intérêt et la complexité est alors en .
Annexes
Bibliographie
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein (trad. de l'anglais), Algorithmique : Cours avec 957 exercices et 158 problèmes, Dunod, [détail de l’édition], p. 24,45
- (en) Oded Gordreich, Computational Complexity : A Conceptual Perspective., Cambridge, Cambridge University Press, , 606 p. (ISBN 978-0-521-88473-0 et 0-521-88473-X), p. 32
