357 votes

Complexité algorithmique de la séquence de Fibonacci

Je comprends la notation Big-O, mais je ne sais pas comment calculer pour de nombreuses fonctions. En particulier, j’ai essayé de comprendre la complexité du calcul de la version naïve de la séquence de Fibonacci :

Quelle est la complexité du calcul de la séquence de Fibonacci et comment est-il calculé ?

402voto

Mehrdad Afshari Points 204872

Le modèle de la fonction de temps pour calculer Fib(n) comme la somme des temps de calcul de l' Fib(n-1) plus le temps de calcul de l' Fib(n-2) plus le temps de les ajouter ensemble (O(1)).

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

- Vous résoudre cette relation de récurrence (à l'aide des fonctions génératrices, par exemple) et vous aurez la réponse.

Alternativement, vous pouvez dessiner la récursivité de l'arbre, ce qui aura de la profondeur n et intuitivement comprendre que cette fonction est asymptotiquement O(2n). Ensuite, vous pouvez prouver votre conjecture par induction.

Base: n = 1 est évident

Supposons T(n-1) = O(2n-1), donc

T(n) = T(n-1) + T(n-2) + O(1) qui est égal à

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

Toutefois, comme indiqué dans un commentaire, ce n'est pas le serré lié. Un fait intéressant à propos de cette fonction est que le T(n) est asymptotiquement la même que la valeur de Fib(n) puisque les deux sont définis comme

f(n) = f(n-1) + f(n-2).

Les feuilles de la récursivité de l'arbre renvoie toujours 1. La valeur de Fib(n) est la somme de toutes les valeurs retournées par les feuilles de la récursivité de l'arbre, qui est égal au nombre de feuilles. Puisque chaque feuille va prendre O(1) pour calculer, T(n) est égal à Fib(n) x O(1). Par conséquent, le resserrement lié à cette fonction est la suite de Fibonacci lui-même (~θ(1.6n)). Vous pouvez trouver cette serré lié en utilisant des fonctions comme je l'avais mentionné ci-dessus.

148voto

Jason Cohen Points 36475

Il suffit de demander vous-même combien de déclarations ont besoin pour exécuter pour F(n) pour terminer.

Pour F(1), la réponse est 1 (la première partie du conditionnel).

Pour F(n), la réponse est F(n-1) + F(n-2).

Donc la fonction qui satisfait à ces règles? Essayez unn:

unn == a(n-1) + a(n-2)

Diviser par un(n-2):

un2 == un + 1

Pour résoudre a et vous obtiendrez (1+sqrt(5))/2, autrement connu comme le nombre d'or.

Donc ça prend du temps exponentiel.

34voto

J.P. Points 16

Je suis d'accord avec pgaur et rickerbh, récursif de fibonacci de la complexité est O(2^n).

Je suis venu à la même conclusion par un peu simpliste, mais je crois toujours valide le raisonnement.

Tout d'abord, il est tout au sujet de trouver comment beaucoup de fois récursif de la fonction de fibonacci F() à partir de maintenant ) est appelée lors du calcul du n-ième nombre de fibonacci. Si elle est appelée une fois par numéro dans la séquence de 0 à n, alors nous avons O(n), s'il est appelé à la n des temps, pour chaque numéro, alors on obtient O(n*n) ou O(n^2), et ainsi de suite.

Ainsi, lorsque F() est appelée pour un nombre n, le nombre de fois où F() est appelée pour un nombre entre 0 et n-1 grandit à mesure que nous nous approchons de 0.

Comme première impression, il me semble que si on le met dans un mode visuel, le dessin d'une unité en fonction du temps F() est appelée pour un nombre donné, humide obtenir une sorte de forme de pyramide (qui est, si nous centre unités horizontalement). Quelque chose comme ceci:

n              *
n-1            **
n-2           ****  
...
2           ***********
1       ******************
0    ***************************

Maintenant, la question est de savoir quelle est la vitesse de base de cette pyramide élargissant à mesure que n augmente?

Prenons un cas concret, par exemple F(6)

F(6)                 *  <-- only once
F(5)                 *  <-- only once too
F(4)                 ** 
F(3)                ****
F(2)              ********
F(1)          ****************           <-- 16
F(0)  ********************************    <-- 32

Nous voyons F(0) est appelée 32 fois, ce qui est 2^5, qui, pour cet échantillon est de 2^(n-1).

Maintenant, nous voulons savoir combien de fois F(x) est appelée à tous, et nous pouvons voir le nombre de fois que F(0) est appelée n'est qu'une partie de cela.

Si nous mentalement déplacer tous les *'partir de F(6) F(2) les lignes en F(1), nous voyons que F(1) et F(0) sont maintenant égaux en longueur. Ce qui signifie, le temps total F() est appelée lorsque n=6 est 2x32=64=2^6.

Maintenant, en termes de complexité:

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)

31voto

Bob Cross Points 13552

Il y a une très belle discussion de ce problème spécifique au cours au MIT. À la page 5, ils font valoir que, si l'on suppose qu'un ajout d'une unité de calcul, le temps nécessaire pour calculer Fib(N) est très étroitement liée à la suite de Fib(N).

Comme un résultat, vous pouvez passer directement à la très bonne approximation de la suite de Fibonacci:

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

et dire, par conséquent, que le pire des cas, les performances de l'algorithme naïf est

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS: Il y a une discussion de la forme fermée de l'expression de la n-ième nombre de Fibonacci sur Wikipedia si vous souhaitez plus d'informations.

10voto

Dave L. Points 19623

Il est limité à l'extrémité inférieure par 2^(n/2) et à l'extrémité supérieure par 2 ^ n (comme indiqué dans d'autres commentaires). Et un fait intéressant de cette implémentation récursive est qu’elle possède une limite asymptotique étroite de Fib (n) lui-même. Ces faits peuvent être résumés:

 T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)
 

La limite étroite peut être réduite davantage en utilisant sa forme fermée si vous le souhaitez.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X