Discussion :

[rvfranck]

Salut,

Quelqu'un pourrait m'aider à montrer que la borne inférieure du tri rapide est nlogn?
j'ai trouvé ce lien mais je ne pige pas trop ce qu'il entend par arbre de décision.

Merci d'avance.

[pseudocode]

Quelqu'un pourrait m'aider à montrer que la borne inférieure du tri rapide est nlogn?

??

Je suppose que la question est "Montrer que la complexité minimum de l'algorithme du tri-rapide est n.log(n)". c'est ca ?

[rvfranck]

oui, effectivement.

[pseudocode]

Et bien la complexité minimale du quicksort c'est lorsque l'arbre est parfaitement équilibré. A chaque itération les sous-listes sont partagées en deux moitiés égales.

iteration 0: 1 liste de taille n
iteration 1: 2 listes de taille n/2
iteration 2: 4 listes de taille n/4
iteration 3: 8 listes de taille n/8
...
iteration i: 2^i listes de taille n/2^i
...
iteration max-1: 2^(max-1) = n/2 listes de taille 2
iteration max: 2^max = n listes de taille 1

La complexité est donc
C = (1)*n + (2)*n/2 + (4)*n/4 + ... + (n/4)*4 + (n/2)*2
C = n + n + n + ....

Le tout est de savoir combien il y a de terme dans la suite '...'
Il y en a "max" tel que "2^max = n", donc max = log(n)/log(2)

la complexite est donc:

C = n * log(n)/log(2) = O(n*log(n))

[rvfranck]

??

Je suppose que la question est "Montrer que la complexité minimum de l'algorithme du tri-rapide est n.log(n)". c'est ca ?

Je conclus donc que j'ai pas bien saisi ta question. En fait on me demande de montrer que dans le pire des cas, le temps du quicksort est dans oméga (nlogn).

En procédant de la même manière et en changeant les = en >= cela reste t'il toujours correct dans le cas favorable?

[rvfranck]

En procédant de la même manière et en changeant les = en >= cela reste t'il toujours correct dans le cas favorable?

[Jedai]

En fait on me demande de montrer que dans le pire des cas, le temps du quicksort est dans oméga (nlogn).

Ca va être difficile vu que c'est faux... Dans le pire des cas, la complexité du quicksort est en O(n^2).

--
Jedaï

[rvfranck]

C'est faux? je croyais pourtant que les tris par comparaison étaient tous dans oméga(nlgn). dans toutes les situations.
Ou alors le tri rapide n'est pas un tri par comparaison? peut être je me trompe, je vais vérifier.

Je précise quand même que O(n^2) est un majorant, mais moi je parle de omega, le minorant.

[pseudocode]

En fait on me demande de montrer que dans le pire des cas, le temps du quicksort est dans oméga (nlogn).

Je précise quand même que O(n^2) est un majorant, mais moi je parle de omega, le minorant.

Faudrait savoir ce que tu veux.

Dans "LE" pire des cas le quicksort est en O(n^2). Dans les autres cas il est proportionnelle a n*log(n).