Petite remarque:
O(1000000 n) = O(n)
O(k^2 + 100 k) = O(k^2)
On garde que le terme de plus haut degré (dans les expressions polynomiales) sinon que le terme qui «croit le plus vite».
F(x) = O(g(x)) <=>
Il existe K tel que F(x)<=K*g(x) pour x assez grand.
Donc pour g(x) on vire la constante devant et tout ce qui sert à rien. On s'arrange pour que g(x) soit le plus simple possible.
Pour être plus précis on peut utiliser un ~ (équivalance).
On a alors (en simplifiant un peu, car on néglige le cas ou g(x) prend parfois 0)
F(x) ~ g(x) <=> F(x)/g(x) -> 1
[^] # Re: Avancées technologiques du prochain Kernel
Posté par Cédric Foll . En réponse à la dépêche Avancées technologiques du prochain noyau Linux. Évalué à 5.
O(1000000 n) = O(n)
O(k^2 + 100 k) = O(k^2)
On garde que le terme de plus haut degré (dans les expressions polynomiales) sinon que le terme qui «croit le plus vite».
F(x) = O(g(x)) <=>
Il existe K tel que F(x)<=K*g(x) pour x assez grand.
Donc pour g(x) on vire la constante devant et tout ce qui sert à rien. On s'arrange pour que g(x) soit le plus simple possible.
Pour être plus précis on peut utiliser un ~ (équivalance).
On a alors (en simplifiant un peu, car on néglige le cas ou g(x) prend parfois 0)
F(x) ~ g(x) <=> F(x)/g(x) -> 1