Bonsoir,
Je ne comprends pas pourquoi l'affichage des entiers entre 1 et n! est en complexité au moins linéaire et pas au moins exponentielle. J'ai joint le sujet de l'examen.
Merci
Bonjour,
Le calcul du factoriel est réalisable en temps linéaire. L'affichage des entiers entre 1 et n! est également réalisable en temps linéaire. Voici un exemple d'algorithme:
factoriel
entrée: n
sortie: rien
fact <- 1
Pour i de 2 à n
fact <- fact * i
Pour i de 1 à fact
afficher i
On observe bien que l'algorithme a une complexité O(n). Evidemment, n! pourrait être très grand suivant la valeur de n. Cela dit, si on demandait d'afficher tous les nombres entre 1 et n et que n valait par exemple 1'000'000'000, on considérerait quand même que l'algorithme a une complexité linéaire.
Oui je suis d’accord avec votre algorithme mais je ne comprends pas pourquoi quand on affiche toutes les valeurs entre 1 et fact on reste en O(n) parce que la boucle fera n! tours de boucle et donc sera en O(n!) et non pas O(n) non ?
je crois que tu as raison, elle fera O(n+n!), je crois que si on fait :
Pour i de 1 à n
fact<---fact*i;
afficher fact;
ça devrait être en 0(n)
Oui cette boucle est en O(n) mais elle va afficher toutes les factorielles entre 1 et n! (1!, 2!, 3!,..., n!) et non pas tous les entiers entre 1 et n!
Attention ! Attention !! Par rapport à quoi la question demande-t-elle d'exprimer la complexité ?....