Voir la source de 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 [[complexité en temps|en temps]] ou [[complexité en espace|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 [[Ressource (informatique)|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 d'un algorithme|terminaison]].

La complexité dans le pire des cas permet de comparer l'efficacité de deux algorithmes. Elle s'oppose à la [[complexité en moyenne des algorithmes|complexité en moyenne]].

== Exemple ==
Pour la recherche d'un élément dans une  [[liste (structure de données)|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#Pivot arbitraire|tri rapide avec choix du pivot arbitraire]] sur une liste de taille <math>n</math> a une complexité en <math>O(n\log(n))</math>sur des permutations aléatoires. Toutefois, si l'entrée est déjà triée, le principe [[diviser pour régner (informatique)|diviser pour régner]] perd son intérêt et la complexité est alors en <math>O(n^2)</math>.

== Annexes ==
=== Bibliographie ===

* {{Cormen3fr
| passage=24,45
}}
* {{Ouvrage
|langue=en
|prénom1=Oded
|nom1=Gordreich
|titre=Computational Complexity
|sous-titre=A Conceptual Perspective.
|éditeur=Cambridge University Press
|lieu=Cambridge
|année=2008
|pages totales=606
|passage=32
|isbn=978-0-521-88473-0
|isbn2=0-521-88473-X
}}

=== Liens externes ===
* {{Lien web | url=http://www.lifl.fr/~tison/AAC/newres/compbab.pdf | titre=Complexité des algorithmes : rappel des définitions de base }}

=== Articles liés ===
* [[Worst-case execution time]]

{{Portail|informatique théorique}}

[[Catégorie:Théorie de la complexité des algorithmes]]
[[Catégorie:Algorithmique]]