Discussion :

[Nemerle]

Ok, mais j'ai eu le même sursaut que Prom@ld: on parle de O(Z) polynomial quand Z est une variable "linéaire"... enfin y a pas mort d'homme

[Jedai]

Ok, mais j'ai eu le même sursaut que Prom@ld: on parle de O(Z) polynomial quand Z est une vairable "linéaire"... enfin y a pas mort d'homme

Oui mais linéaire en quoi ? On peut considérer qu'il y a 2^b nombres à coder, et donc que n=2^b est l'unité fondamentale de l'algorithme, qui est donc en O(n), linéaire. Ou que l'unité fondamentale est plutôt b, le nombre de bits, et poser n=b, alors l'algorithme est exponentiel en O(2^n).
C'est une question importante dès lors qu'on parle d'algorithmes numériques, où beaucoup d'algorithmes sont linéaires... si l'on prend n=nombre à traiter, mais c'est rarement la complexité qui nous intéresse, on préfère poser n=log(nombre à traiter).

--
Jedaï

[PRomu@ld]

En fait, la plupart du temps, on prend pour référence les opération atomiques au niveau processeur, ainsi, on dira qu'une addition est en O(1) peu importe le nombre de bits, l'unité de base est donc le nombre. Ca permet aussi de faire un lien entre théorie et pratique.

On peut considérer qu'il y a 2^b nombres à coder, et donc que n=2^b est l'unité fondamentale de l'algorithme, qui est donc en O(n), linéaire. Ou que l'unité fondamentale est plutôt b, le nombre de bits, et poser n=b, alors l'algorithme est exponentiel en O(2^n).

En fait pas tout à fait, l'algorithme est toujours linéaire dans la mesure où les opérations sur n bits s'effectuent en O(1) (si n < taille mot machine). Parler d'algorithme exponentiel n'a de sens que si tu fait tout toi même et que la donnée de base est le bit (ce qui dans la pratique est rarement le cas).