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

    Posté par . En réponse à la dépêche Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6. Évalué à -3.

    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 dis déjà plus haut, O(n*log(n)) est la meilleur complexité possible pour un algo de tri qui ne fait pas de supposition sur les données. Si on en fait, on peut trouver des algo meilleurs, par exemple en O(n). D'autre part, quicksort est en O(n*log(n)) au meilleur cas au pire cas il est en O(n^2). Par exemple, si le but est de trier une liste qui est déjà presque triée (typiquement si on rajoute des données à une liste triée), alors quicksort est presque en O(n^2). Si on essaie de trier une liste déjà trier, quicksort est en O(n^2).