Complexité de l'algorithme récursif factoriel
Aujourd'hui dans la classe de mon professeur a écrit sur le tableau noir de cette factorielle récursive de l'algorithme:
int factorial(int n) {
if (n == 1)
return 1;
else
return n * factorial(n-1);
}
Elle a dit qu'elle a un coût de T(n-1) + 1
.
Puis à l'itération de la méthode, elle a dit que T(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + j
alors l'algorithme s'arrête lorsque n - j = 1
donc j = n - 1
.
Après cela, elle a substitué j
dans T(n-1) + 1
et obtenu T(1) + n-1
.
Elle a déclaré que, pour que n-1 = 2(log2n-1)et donc le coût de l'algorithme est exponentielle.
J'ai vraiment perdu les deux dernières étapes. Pouvez s'il vous plaît quelqu'un m'expliquer à moi?
source d'informationauteur Francesco Bonizzi
Vous devez vous connecter pour publier un commentaire.
Nous allons commencer avec l'analyse de cet algorithme. On peut écrire une relation de récurrence pour le montant total de travail effectué. Comme une base de cas, vous n'avez qu'une unité de travail, lorsque l'algorithme est exécuté sur une entrée de taille 1, donc
Pour une entrée de taille n + 1, l'algorithme fait une unité de travail dans la fonction elle-même, puis il fait un appel à la même fonction sur une entrée de taille n. Donc
Si vous développez les termes de la récidive, vous obtenez ce que
Donc, en général, cet algorithme nécessite n unités de travail (c'est à dire T(n) = n).
La prochaine chose que votre professeur a dit qu'
Cette affirmation est vraie, parce que 22x = x pour tout x différent de zéro, puisque l'exponentiation et logarithmes sont inverses l'exploitation de l'un à l'autre.
La question est donc: est ce temps polynomial ou exponentiel de temps? J'avais classer cela comme pseudopolynomial temps. Si vous considérez l'entrée x comme un nombre, alors le moteur d'exécution est en effet un polynôme en x. Cependant, en temps polynomial est formellement définie de telle façon que le moteur d'exécution de l'algorithme doit être un polynôme en fonction du nombre de bits utilisés pour spécifier les données d'entrée du problème. Ici, le nombre x peut être spécifié dans seulement Θ(log x) bits, de sorte que le temps d'exécution du 2log x est techniquement considéré comme temps exponentiel. J'ai écrit à propos de ce que la longueur de cette première réponseet je vous recommande de regarder pour une explication plus approfondie.
Espérons que cette aide!