Discussion :

[t-student]

Bonjour

je désire avoir une explication de l'ordre de complexite de l'algo QuickSort(tri rapide) dans le meilleur cas (nlog(n)) et dans le pire cas n^2 sachant que l'opération de base est la comparaison entre deux élements ?

est ce que l'évaluation du pire cas vient d'une intuition ou bien il existe une mehode pour le connaitre sachant qu'il s'agit du cas où le pivot est l'élement le plus petit ! de même pour le meilleur cas - le pivot est toujours median -

merci de votre aide

[Jedai]

est ce que l'évaluation du pire cas vient d'une intuition ou bien il existe une mehode pour le connaitre sachant qu'il s'agit du cas où le pivot est l'élement le plus petit ! de même pour le meilleur cas - le pivot est toujours median -

Il suffit juste de dérouler l'algorithme : dans le pire des cas, il y aura n étapes (et à l'étape i, n-i comparaisons), dans le meilleur, il n'y aura que log2 n étapes (et à l'étape i, n-2^(i)+1 comparaisons).
La partie compliquée dans l'analyse de la complexité du quicksort, c'est la complexité en moyenne.

--
Jedaï

[t-student]

dans le meilleur, il n'y aura que log2 n étapes (et à l'étape i, n-2^(i)+1 comparaisons).
Jedaï

je crois que dans le meilleur cas ça aurait du être n/(2^(i-1)) comparaison pour l'étape i ! si je ne me trompe pas ???

lol

[Jedai]

je crois que dans le meilleur cas ça aurait du être n/(2^(i-1)) comparaison pour l'étape i ! si je ne me trompe pas ???

A priori tu te trompes, tu comptes seulement la moitié des comparaisons (et avec des petites erreurs en plus). En fait il y a autant de comparaisons à effectuer que d'éléments non-pivots à chaque étape. Dans le pire des cas, on rajoute un pivot à chaque étape, alors que dans le meilleur, on en rajoute 2^(i-1), en cumulé, ça fait bien la formule que j'ai donné.

--
Jedaï

[ToTo13]

Bonjour,

je pense aussi que tu te trompes.

Pour ce qui est de la compléxité du QuickSort :
- O(N log N) est la complexité moyenne et non dans le meilleur des cas. On la calcule après de nombreux calculs de proba que je ne saurai expliquer mais que tu trouveras très certainement sur google.
- O(N^2) esl la complexité dans le pire des cas. Elle apparaît lorsque le pivot est toujours la première case de la partition à trier ET si le tableau à trier est déjà trié mais dans le sens inverse de celui qui l'on souhaite. Auquel cas la sous partition à trier est de taille N-1 de celle que l'on traite => N(N+1)/2 opération (de mémoire, mais je me trompe peut être).

[Jedai]

- O(N log N) est la complexité moyenne et non dans le meilleur des cas.

Les deux mon capitaine... D'une part la complexité moyenne est toujours un O() de la complexité dans le meilleur des cas , et d'autre part, comme je viens de le montrer, la complexité dans le meilleur des cas est vraiment équivalente à du N log N.

- O(N^2) esl la complexité dans le pire des cas. Elle apparaît lorsque le pivot est toujours la première case de la partition à trier ET si le tableau à trier est déjà trié mais dans le sens inverse de celui qui l'on souhaite. Auquel cas la sous partition à trier est de taille N-1 de celle que l'on traite => N(N+1)/2 opération (de mémoire, mais je me trompe peut être).

"N(N-1) / 2" comparaisons en fait, si tu te rapportes à mon analyse. Par ailleurs le pire des cas se produit également si le tableau est trié dans le bon sens (sous condition qu'on prenne comme pivot la première case de la partition), on peut aussi avoir d'autre cas. Le pire cas est celui où le pivot choisi à chaque étape (quelle que soit la façon) est indistinctement le maximum ou le minimum de sa partition, ce que tu décris n'est qu'un cas particulier.

--
Jedaï