Eh non! Les équivalences, ordres et negligeabilites pour les suites (c'est de ça qu'on parle), ça se passe à l'infini. Quand t(n) est le temps pour traiter n données, que l'algo soit en O(n) veut dire t(n)/n borné sur un voisinage de l'infini.
Et n'en déplaise à certains, 100 ou 200 c'est pas encore tout à fait l'infini.
C'est d'ailleurs le problème. Un algo extra sensass en O(1) peut très bien être super merdique : imagine que le temps soit du type constant égal à 10^100^100 ( unités je-sais-pas-quoi). L'algo est en O(1) mais ça veut pas dire grand chose.
Mais là c'est pas très parlant. Imagine un algo en O(ln n). Je crois que c'est considéré comme pas mal. Seulement, pour n<10000, il s'écrit e^n+n^321 et ensuite c'est e^10000+10000^321+ln n. C'est bien pour les grosses quantités de données, mais faut pas l'utiliser si tu en a 10.
La notation O(n^2) ne présage rien du comportement entre 100 et 200
[^] # Re: Avancées technologiques du prochain Kernel
Posté par mickabouille . En réponse à la dépêche Avancées technologiques du prochain noyau Linux. Évalué à 4.
Et n'en déplaise à certains, 100 ou 200 c'est pas encore tout à fait l'infini.
C'est d'ailleurs le problème. Un algo extra sensass en O(1) peut très bien être super merdique : imagine que le temps soit du type constant égal à 10^100^100 ( unités je-sais-pas-quoi). L'algo est en O(1) mais ça veut pas dire grand chose.
Mais là c'est pas très parlant. Imagine un algo en O(ln n). Je crois que c'est considéré comme pas mal. Seulement, pour n<10000, il s'écrit e^n+n^321 et ensuite c'est e^10000+10000^321+ln n. C'est bien pour les grosses quantités de données, mais faut pas l'utiliser si tu en a 10.
La notation O(n^2) ne présage rien du comportement entre 100 et 200
Le rabat joie de service