Re: [HS ?] Ordre de complexité d'un alogrithme

Ah oui, je tiens à préciser que la meilleur complexité pour les algos de tri c'est en O(n*log(n)) (quicksort) et pas en O(n). Bon, comme je le dit plus haut, ce n'est pas vrai, c'est seulement O(n*log(n)) est la complexité limite d'un algo de tri si on ne fait pas de suppositions sur les données, sinon il existe mieux (je donne un exemple avec un algo en O(n)). D'autre part quicksort est en O(n*log(n)) uniquement en moyenne, au pire cas il est en O(n^2). Notamment, pour retrier une liste presque triée, quicksort est quasiment en O(n^2) (en fait quicksort est au plus lent si on lui demande de trier une liste qui l'est déjà).