Pour ceux qui ne suivent pas: Oui, il est possible d'avoir des tris en O(n), mais les hypothèses sur les données à trier sont plus fortes que celles dont on a besoin pour les tris "standards".
Pour ceux qui ne suivent vraiment pas: Un tri en O(n) signifie que la complexité du tri est linéaire selon la taille de l'entrée (n). Ce qui, aux constantes près, équivaudrait en temps à un simple parcours des n éléments de l'entrée, ce qui est très bon (les tris courants ne descendent pas au dessous de O(n.log(n)) si j'ai bonne mémoire).
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. Mais comme les notations asymptotiques ne tiennent pas compte des constantes, ça ne se voit pas.
Quelqu'un pour infirmer/confirmer/completer/me faire interner?
[^] # Re: Soft de peer to perr
Posté par Larry Cow . En réponse au journal Soft de peer to perr. Évalué à 1.
Pour ceux qui ne suivent vraiment pas: Un tri en O(n) signifie que la complexité du tri est linéaire selon la taille de l'entrée (n). Ce qui, aux constantes près, équivaudrait en temps à un simple parcours des n éléments de l'entrée, ce qui est très bon (les tris courants ne descendent pas au dessous de O(n.log(n)) si j'ai bonne mémoire).
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. Mais comme les notations asymptotiques ne tiennent pas compte des constantes, ça ne se voit pas.
Quelqu'un pour infirmer/confirmer/completer/me faire interner?