Allez, je me lance pour faire la démo du n*log(n).
Bon, considérons les listes des entiers de 1 à n.
Il y en a n! (n places possibles pour "n" puis (n-1) pour "n-1" car la place de
"n" est prise etc.).
On peut représenter un tri par comparaisons par un arbre de décision.
Au début, je décide de comparer x et y
Si x>y alors
-- je compare z et t
-- si z>t alors...
-- si t<z alors...
Si y<x alors
-- je compare u et i
-- si u>i alors...
-- si u<i alors...
Le feuilles de l'arbre correspondent au moment où le tri s'arrête. « J'ai fini.
Ouai! »
Si on se donne une liste particulière, le fonctionnement de l'algorithme
correspond à un chemin particulier dans cet arbre et deux listes différentes
vont correspondre à deux chemins distincts.
Il faut donc n! feuilles dans notre arbre de décision. Intuitivement, si on veut
que le plus long des chemins soit le plus cours possible, il faut que l'arbre
soit équilibré, voir même que ce soit un arbre binaire complet. Or, le nombre de
feuilles d'un arbre binaire complet de hauteur h est 2^h.
La hauteur de l'arbre de décision doit donc vérifier 2^h>n! et donc h>log(n!).
Or la formule de stirling donne n!~\sqrt{2\pi}(n/e)^n donc log(n!)~n*log(n) et
donc, la profondeur de notre arbre de décision est donc au minimum
O(n*log(n)).
[^] # Re: Hum
Posté par fmaz fmaz . En réponse au journal M'enfin ?? .... Évalué à 3.
Bon, considérons les listes des entiers de 1 à n.
Il y en a n! (n places possibles pour "n" puis (n-1) pour "n-1" car la place de
"n" est prise etc.).
On peut représenter un tri par comparaisons par un arbre de décision.
Au début, je décide de comparer x et y
Si x>y alors
-- je compare z et t
-- si z>t alors...
-- si t<z alors...
Si y<x alors
-- je compare u et i
-- si u>i alors...
-- si u<i alors...
Le feuilles de l'arbre correspondent au moment où le tri s'arrête. « J'ai fini.
Ouai! »
Si on se donne une liste particulière, le fonctionnement de l'algorithme
correspond à un chemin particulier dans cet arbre et deux listes différentes
vont correspondre à deux chemins distincts.
Il faut donc n! feuilles dans notre arbre de décision. Intuitivement, si on veut
que le plus long des chemins soit le plus cours possible, il faut que l'arbre
soit équilibré, voir même que ce soit un arbre binaire complet. Or, le nombre de
feuilles d'un arbre binaire complet de hauteur h est 2^h.
La hauteur de l'arbre de décision doit donc vérifier 2^h>n! et donc h>log(n!).
Or la formule de stirling donne n!~\sqrt{2\pi}(n/e)^n donc log(n!)~n*log(n) et
donc, la profondeur de notre arbre de décision est donc au minimum
O(n*log(n)).
Fini.