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.
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Discussion :
[Algorithmique] Déterminer la borne inférieure du Tri rapide.
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.
Envoyé par 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 ?
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
oui, effectivement.
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))
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
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).
Je suppose que la question est "Montrer que la complexité minimum de l'algorithme du tri-rapide est n.log(n)". c'est ca ?
En procédant de la même manière et en changeant les = en >= cela reste t'il toujours correct dans le cas favorable?
En procédant de la même manière et en changeant les = en >= cela reste t'il toujours correct dans le cas favorable?
Ca va être difficile vu que c'est faux... Dans le pire des cas, la complexité du quicksort est en O(n^2).
--
Jedaï
C'est faux? je croyais pourtant que les tris par comparaison étaient tous dans oméga(nlgn).
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.
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).
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Je n'ai donc rien compris à cette affaire de notations asymptôtiques.
Je pensais que lorsqu'on est dans un cas (favorable, défavorable, moyen) on determinait le temps maximum que prend l'algo (la notation O) et le temps minimum que prend l'algo (la notation omega) dans ce cas. autrement dit:
- cas favorable on a un O et un omega
- cas defavorable on a un O et un omega
- cas moyen on a un O et un omega.
Apparament ce n'est pas celà!!!
Lis le chapitre à partir de la page 33 (numérotation latex) : ftp://ftp-developpez.com/lapoire/alg...orithmique.pdf
Sinon, la page Wikipédia donne un résumé pas trop mal.
En fait si tu parles d'un oméga, il est exact de dire que dans le pire des cas, le quicksort est en oméga de n log n, mais c'est parfaitement inutile, on pourrait aussi bien dire qu'il est en oméga 1... Généralement en informatique quand on utilise O ou Oméga, on cherche toujours les bornes les plus serrées possibles, or dans le pire des cas, quicksort est en Oméga n^2, dire qu'il est en Oméga n log n c'est donc risquer une confusion (que tu fais visiblement, voir la suite).
En gros, tu as l'air de confondre quicksort et tri par comparaison en général : ce que tu veux ce n'est pas une preuve spécifique à quicksort (et surtout pas à son pire cas, puisque celui-ci est en Oméga n^2...), mais bien une preuve générale pour tous les tris par comparaisons qu'il sont dans Oméga n log n.
Pour en revenir à ta question, un arbre de décision c'est un arbre où les noeuds sont des tests et où l'on suit l'une ou l'autre branche selon le résultat de ce test. Pour les tris par comparaisons, tous les tests autorisés sont les comparaisons entre deux éléments du tableau, on peut ainsi établir une taille minimale (et suffisante théoriquement) pour l'arbre de décision qui prend une séquence quelconque et la range.
--
Jedaï
Merci beaucoup de m'aider à comprendre.
Maintenant je voudrais juste savoir, pourquoi on a l'habitude d'exprimer l'ordre avec la notation O qu'on soit dans le pire, le meilleur ou le moyen?
La definition de O dit qu'il permet de borner supérieurement la fonction, pourquoi on ne l'utilise pas uniquement dans le pire des cas?
Je ne sais pas si c'est ce que tu tentes de m'expliquer ici, mais je ne pige pas trop bien.
c'est vrai que j'ai la tête un peu dure, mais je n'y peu rien
C'est ce qu'on fait habituellement.
Pour le quicksort c'est un peu particulier car il n'y a qu'un seul cas ou il est en O(n^2): c'est le cas ou la liste est deja triée (a l'endroit ou a l'envers). Dans TOUS les autres cas, il est en O(n*log(n)).
En fait, la complexité du quicksort est O(K*n) avec K entre log(n) et n.
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
La plupart des algorithmes ne diffèrent pas tant entre le pire et le meilleur cas, de plus O est souvent utilisé à la place de théta (borne inférieur et supérieur dite "serrée"), sans doute parce que théta est plus difficile à taper (une lettre grecque et tout ça...). De plus réfléchis-y un peu : qu'est-ce qui est le plus intéressant pour un informaticien qui veut utiliser un algo, la borne supérieure ou la borne inférieure de sa complexité ???
Ce résultat sur le oméga des tris par comparaisons est intéressant parce qu'il permet de prouver que l'on ne peut pas faire mieux que les algorithmes actuels (pas beaucoup mieux en tout cas) mais oméga est généralement nettement moins utile.
--
Jedaï
Salut,
Oublions un peu les tris et dites moi ce que veut dire O(n) tout court, O(n) en pire cas et O(n) en cas favorable.
Merci.
http://fr.wikipedia.org/wiki/Notations_de_Landau
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Une fois de plus merci pour le lien, même s'il ne m'a pas fait avancer.
Vous savez, parfois il ne suffit pas de lire pour comprendre. J'ai lu pas mal de bouquin sur les notations asymptôtiques et chaque jour que j'ouvre un nouveau document sur le sujet, je trouve que ce que je pensais vrai est faux. Donc j'interprète mal ce que je lis!
Et si je pose ma question ici c'est pour avoir une interprètation autre que la mienne.
J'ai consulté ce lien, mais jusque là je ne trouve pas de reponse à mes intérrogations.
Merci encore.
comme le dit wikipedia:
f(x) = O(g(x)) quand x-->oo ssi il existe n,c tel que |f(x)|<c.|g(x)| pour tout x>n
Visuelement ca veut dire que pour x>n la courbe f() sera toujours en dessous de la courbe c.g(). On peut dire abusivement que la "courbure" de la courbe f() est égale ou moins grande que celle de g(), et donc que f() ne pourra jamais "couper" g().
Et quelle sont ces interrogations ?J'ai consulté ce lien, mais jusque là je ne trouve pas de reponse à mes intérrogations.
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Répondre avec citation
Partager