> Si je me souviens bien on avait démontré qu'un algo de tri était au mieux en O(n ln(n)).
Avec des hypothèses, tout de même.
Parce que si on ne trie que des entiers de 32bits (ou toute autre taille bornée), on peut alors avoir un tri linéraire (tri radix par exemple). Une recherche très rapide sur google m'a donné : http://fr.wikipedia.org/wiki/Tri(...)
En archi, on forme aussi des réseaux de tri qui font leur boulot en temps linéraire.
La borne donnée n'est valable que pour les tris basés sur des comparaisons successives.
[^] # Re: Avancées technologiques du prochain Kernel
Posté par Vincent Danjean . En réponse à la dépêche Avancées technologiques du prochain noyau Linux. Évalué à 1.
Avec des hypothèses, tout de même.
Parce que si on ne trie que des entiers de 32bits (ou toute autre taille bornée), on peut alors avoir un tri linéraire (tri radix par exemple). Une recherche très rapide sur google m'a donné : http://fr.wikipedia.org/wiki/Tri(...)
En archi, on forme aussi des réseaux de tri qui font leur boulot en temps linéraire.
La borne donnée n'est valable que pour les tris basés sur des comparaisons successives.