Version imprimable
Bonjour :D
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 :ccool:
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).Citation:
Envoyé par t-student
La partie compliquée dans l'analyse de la complexité du quicksort, c'est la complexité en moyenne.
--
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 :( ???Citation:
Envoyé par Jedai
lol
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é.Citation:
Envoyé par t-student
--
Jedaï
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).
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.Citation:
Envoyé par ToTo13
"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.Citation:
Envoyé par ToTo13
--
Jedaï
8O ?!Citation:
Envoyé par Jedai
la complexité moyenne du tri à bulles avec sortie est O(N) ???
Ok, la phrase n'était pas très claire, je voulais dire que si la complexité moyenne est en f(n) alors la complexité dans le meilleur des cas est en O(f(n)).Citation:
Envoyé par pseudocode
--
Jedaï
Ah, ok. ;)Citation:
Envoyé par Jedai
Lapalice, si tu nous regardes :coucou: