Cependant, il me semble que les fameux tris en O(n), même s'ils restent très supérieurs aux algorithmes classiques quand ils sont applicables, sont en fait en O(n.m) avec m une "très grosse" constante.
Pas forcément si grosse que ça la constante (puisqu'elle dépend grandement de la distribuion des données) mais, oui, elle est là et personne ne veut en parler.
Par exemple dans l'algo suivant :
soit une entrée de n nombres (dont la distribution est F)
soit m une constante (de préférence plus petite que n)
soient q_i = F^(-1)(i*m/n) pour i entier entre 1 et r-1=E(n/m) (E la partie entière)
et q_0 = -inf et q_r = +inf
soit c la fonction telle que :
c(x)=i si et seulement si q_i <= x < q_(i+1)
c peut être vue comme une équivalence. On a donc r classes d'équivalences. Or on peut classer n nombres en O(n) (avec une complexité mémoire en O(r), donc en O(n/m)... en O(n)).
(classer les nombres consiste à mettre en premeir ceux de la classe 0, en deuxième ceux de la classe 1 etc.)(NB : quicksort est un classement en deux classes qui s'appelle récursivement sur chaque classe)
Une fois classés, il suffit d'appeler sur chaque classe un algo de tri classique. Chaque classe ayant un effectif espéré de m nombres, le tri d'une classe se fait en O(m ln m).
Or il y a r (c'est à dire à peu près n/m) classes donc le tri de toutes les classes coûte :
O(n ln m)
il y a aussi le coût du classement : O(n)
Le tout est en O(n ln m) + O(n), c'est à dire O(n) CQFD et 10 de der.
Et puis ln m c'est pas gros comme constante.
Ok, je mens : la vraie vilaine constante est dans le classement : l'évaluation de F^(-1) pour tout nombre en entrée. Dans la plupart des cas pratiques, cette fonction est dégueulasse. (rien qu'une petite gaussienne est déjà méchante) (Par contre si vos données sont équiréparties, c'est trivial)
Et voilà, je suis un encore plus gros vendeur de mèche.
[^] # Re: Soft de peer to perr
Posté par Christophe GRAND . En réponse au journal Soft de peer to perr. Évalué à 2.
Cependant, il me semble que les fameux tris en O(n), même s'ils restent très supérieurs aux algorithmes classiques quand ils sont applicables, sont en fait en O(n.m) avec m une "très grosse" constante.
Pas forcément si grosse que ça la constante (puisqu'elle dépend grandement de la distribuion des données) mais, oui, elle est là et personne ne veut en parler.
Par exemple dans l'algo suivant :
soit une entrée de n nombres (dont la distribution est F)
soit m une constante (de préférence plus petite que n)
soient q_i = F^(-1)(i*m/n) pour i entier entre 1 et r-1=E(n/m) (E la partie entière)
et q_0 = -inf et q_r = +inf
soit c la fonction telle que :
c(x)=i si et seulement si q_i <= x < q_(i+1)
c peut être vue comme une équivalence. On a donc r classes d'équivalences. Or on peut classer n nombres en O(n) (avec une complexité mémoire en O(r), donc en O(n/m)... en O(n)).
(classer les nombres consiste à mettre en premeir ceux de la classe 0, en deuxième ceux de la classe 1 etc.)(NB : quicksort est un classement en deux classes qui s'appelle récursivement sur chaque classe)
Une fois classés, il suffit d'appeler sur chaque classe un algo de tri classique. Chaque classe ayant un effectif espéré de m nombres, le tri d'une classe se fait en O(m ln m).
Or il y a r (c'est à dire à peu près n/m) classes donc le tri de toutes les classes coûte :
O(n ln m)
il y a aussi le coût du classement : O(n)
Le tout est en O(n ln m) + O(n), c'est à dire O(n) CQFD et 10 de der.
Et puis ln m c'est pas gros comme constante.
Ok, je mens : la vraie vilaine constante est dans le classement : l'évaluation de F^(-1) pour tout nombre en entrée. Dans la plupart des cas pratiques, cette fonction est dégueulasse. (rien qu'une petite gaussienne est déjà méchante) (Par contre si vos données sont équiréparties, c'est trivial)
Et voilà, je suis un encore plus gros vendeur de mèche.