Complexité dans le meilleur des cas

En informatique, dans le cadre de l'analyse de la complexité des algorithmes, la complexité dans le meilleur des cas correspond à la complexité (par exemple en temps) d'un algorithme dans le cas d'exécution le plus favorable possible. 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 inférieure des ressources requises par l'algorithme.

Par exemple, la complexité en temps dans le meilleur des cas correspond au temps d'exécution le plus court que puisse avoir l'algorithme.

La complexité dans le meilleur des cas n'est pas le premier critère à considérer pour comparer des algorithmes entre eux, car on lui préférera la complexité en moyenne ou la complexité dans le pire des cas. En revanche, elle est parfois nettement inférieure à ces deux dernières, et peut donc permettre de favoriser le choix d'un algorithme si l'on sait que les entrées à traiter ont en pratique de bonnes chances de correspondre à des cas optimaux.

Exemple

Le tri à bulles sur une liste de taille $n$ a une complexité en moyenne quadratique (en $O(n^{2})$). En revanche, si l'entrée est déjà triée, la complexité devient linéaire ; il s'agit de la complexité dans le meilleur des cas de cet algorithme. Si l'on sait qu'il y a une chance non négligeable pour que l'entrée à traiter soit déjà triée, il peut être intéressant de privilégier le tri à bulles par rapport à un algorithme comme le tri par tas, qui semble plus rapide dans le cas général mais possède une complexité en $O(n\log n)$ dans tous les cas, et sera donc plus lent dans le cas d'une liste déjà triée. Cet exemple n'est donné que pour illustrer le propos, et il existe en pratique beaucoup d'algorithmes de tri dont certains peuvent se révéler être plus adaptés.

Bibliographie

• Cormen, Leiserson, Rivest et Stein (trad. de l'anglais), Algorithmique : cours avec 957 exercices et 158 problèmes, Paris, Dunod, 2010, 1188 p. (ISBN 978-2-10-054526-1)

Liens externes

• « Complexité des algorithmes : rappel des définitions de base »