La complexité computationnelle de la séquence de Fibonacci

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

int Fibonacci(int n) { if (n <= 1) return n; else return Fibonacci(n - 1) + Fibonacci(n - 2); } 

Quelle est la complexité de calcul de la séquence de Fibonacci et comment est-elle calculée?

Vous modélisez la fonction de temps pour calculer Fib(n) comme une sum de temps pour calculer Fib(n-1) plus le temps pour calculer Fib(n-2) plus le temps pour les additionner ensemble ( O(1) ).

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

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

Vous résolvez cette relation de récurrence (en utilisant des fonctions de génération, par exemple) et vous obtiendrez la réponse.

Alternativement, vous pouvez dessiner l'arbre de récurrence, qui aura la profondeur n et découvrir intuitivement que cette fonction est asymptotiquement O(2 n ) . Vous pouvez alors prouver votre conjecture par induction.

Base: n = 1 est évident

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

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

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

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

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

Les feuilles de l'arbre de récurrence retourneront toujours 1. La valeur de Fib(n) est la sum de toutes les valeurs renvoyées par les feuilles dans l'arbre de récurrence, qui est égale au nombre de feuilles. Puisque chaque feuille prend O (1) pour calculer, T(n) est égal à Fib(n) x O(1) . Par conséquent, la liaison étroite pour cette fonction est la séquence de Fibonacci elle-même (~ θ(1.6 n ) ). Vous pouvez découvrir ce lien étroit en utilisant des fonctions de génération comme je l'ai mentionné ci-dessus.

Demandez-vous simplement combien d’exécutions doivent être exécutées pour que F(n) se termine.

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) .

Alors quelle fonction satisfait à ces règles? Essayez un n (a> 1):

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

Diviser par un (n-2) :

a 2 == a + 1

Résoudre pour a et vous obtenez (1+sqrt(5))/2 = 1.6180339887 , autrement connu sous le nom de nombre d’ or .

Donc, cela prend du temps exponentiel.

Il y a une très belle discussion sur ce problème spécifique chez MIT . À la page 5, ils soulignent que, si vous supposez qu’une addition prend une unité de calcul, le temps nécessaire pour calculer Fib (N) est très étroitement lié au résultat de Fib (N).

En conséquence, vous pouvez passer directement à l’approximation très proche de la série Fibonacci:

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

et dire, par conséquent, que la performance la plus défavorable 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 sur l’ expression de forme fermée du numéro Nth Fibonacci sur Wikipedia si vous souhaitez plus d’informations.

Je suis d’accord avec pgaur et rickerbh, la complexité récursive-fibonacci est O (2 ^ n).

Je suis arrivé à la même conclusion par un raisonnement plutôt simpliste mais je crois encore valable.

Tout d’abord, il s’agit de déterminer combien de fois la fonction récursive de fibonacci (F () à partir de maintenant) est appelée lors du calcul du Nième nombre de fibonacci. S’il est appelé une fois par numéro dans la séquence 0 à n, alors nous avons O (n), s’il est appelé n fois pour chaque nombre, alors nous obtenons O (n * n), ou O (n ^ 2), etc.

Ainsi, lorsque F () est appelé pour un nombre n, le nombre de fois que F () est appelé pour un nombre donné compris entre 0 et n-1 augmente à l’approche de 0.

Comme première impression, il me semble que si on le met de manière visuelle, dessiner une unité par temps F () est appelée pour un nombre donné, humide pour obtenir une sorte de forme de pyramide (c’est-à-dire si on centre les unités horizontalement) ). Quelque chose comme ça:

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

Maintenant, la question est: à quelle vitesse la base de cette pyramide s’élargit-elle à mesure que n grandit?

Prenons un cas réel, 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 

On voit que F (0) est appelé 32 fois, ce qui correspond à 2 ^ 5, ce qui pour cet exemple de cas est 2 ^ (n-1).

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

Si nous déplaçons mentalement tous les * des lignes F (6) à F (2) dans la ligne F (1), nous voyons que les lignes F (1) et F (0) sont maintenant égales en longueur. Ce qui signifie que le total des temps F () est appelé 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) 

Vous pouvez l’agrandir et avoir une visualisation

  T(n) = T(n-1) + T(n-2) < T(n-1) + T(n-1) = 2*T(n-1) = 2*2*T(n-2) = 2*2*2*T(n-3) .... = 2^i*T(ni) ... ==> O(2^n) 

Il est limité à l’extrémité inférieure par 2^(n/2) et à l’extrémité supérieure par 2 ^ n (comme noté 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.

Les preuves des réponses sont bonnes, mais je dois toujours faire quelques itérations à la main pour vraiment me convaincre. J’ai donc dessiné un petit arbre d’appel sur mon tableau blanc et j’ai commencé à compter les nœuds. Je divise mes comptes en nœuds totaux, nœuds feuilles et nœuds intérieurs. Voici ce que j’ai eu:

 IN | OUT | TOT | LEAF | INT 1 | 1 | 1 | 1 | 0 2 | 1 | 1 | 1 | 0 3 | 2 | 3 | 2 | 1 4 | 3 | 5 | 3 | 2 5 | 5 | 9 | 5 | 4 6 | 8 | 15 | 8 | 7 7 | 13 | 25 | 13 | 12 8 | 21 | 41 | 21 | 20 9 | 34 | 67 | 34 | 33 10 | 55 | 109 | 55 | 54 

Ce qui se passe immédiatement, c’est que le nombre de nœuds foliaires est fib(n) . Ce qui a pris quelques itérations supplémentaires, c’est que le nombre de nœuds intérieurs est fib(n) - 1 . Par conséquent, le nombre total de nœuds est 2 * fib(n) - 1 .

Puisque vous déposez les coefficients lors de la classification de la complexité de calcul, la réponse finale est θ(fib(n)) .

Eh bien, selon moi, c’est O(2^n) car dans cette fonction, seule la récursion prend le temps considérable (diviser et conquérir). Nous voyons cela, la fonction ci-dessus continuera dans un arbre jusqu’à ce que les feuilles se rapprochent lorsque nous atteignons le niveau F(n-(n-1)) soit F(1) . Donc, ici, lorsque nous notons la complexité temporelle rencontrée à chaque profondeur d’arbre, la série de sommation est la suivante:

 1+2+4+.......(n-1) = 1((2^n)-1)/(2-1) =2^n -1 

c’est l’ordre de 2^n [ O(2^n) ] .

La version récursive naïve de Fibonacci est exponentielle par conception en raison de la répétition dans le calcul:

A la racine que vous calculez:

F (n) dépend de F (n-1) et F (n-2)

F (n-1) dépend à nouveau de F (n-2) et F (n-3)

F (n-2) dépend à nouveau de F (n-3) et F (n-4)

alors vous avez à chaque niveau 2 des appels récursifs qui gaspillent beaucoup de données dans le calcul, la fonction temps ressemblera à ceci:

T (n) = T (n-1) + T (n-2) + C, avec la constante C

T (n-1) = T (n-2) + T (n-3)> T (n-2) puis

T (n)> 2 * T (n-2)

T (n)> 2 ^ (n / 2) * T (1) = O (2 ^ (n / 2))

Ceci est juste une limite inférieure qui, pour les besoins de votre parsing, devrait suffire mais la fonction temps réel est un facteur de constante par la même formule de Fibonacci et la forme fermée est connue pour être exponentielle du nombre d’or.

En outre, vous pouvez trouver des versions optimisées de Fibonacci en utilisant une programmation dynamic comme celle-ci:

 static int fib(int n) { /* memory */ int f[] = new int[n+1]; int i; /* Init */ f[0] = 0; f[1] = 1; /* Fill */ for (i = 2; i <= n; i++) { f[i] = f[i-1] + f[i-2]; } return f[n]; } 

Ceci est optimisé et ne fait que n pas mais est également exponentiel.

Les fonctions de coût sont définies de la taille d'entrée au nombre d'étapes nécessaires pour résoudre le problème. Lorsque vous voyez la version dynamic de Fibonacci ( n étapes pour calculer la table) ou l'algorithme le plus simple pour savoir si un nombre est premier ( sqrt (n) pour parsingr les diviseurs valides du nombre). vous pouvez penser que ces algorithmes sont O (n) ou O (sqrt (n)) mais ce n'est simplement pas vrai pour la raison suivante: L'entrée de votre algorithme est un nombre: n , en utilisant la notation binary la taille d'entrée d'un entier n est log2 (n) puis effectue un changement variable de

 m = log2(n) // your real input size 

laisser le nombre d'étapes en fonction de la taille d'entrée

 m = log2(n) 2^m = 2^log2(n) = n 

alors le coût de votre algorithme en fonction de la taille d'entrée est le suivant:

 T(m) = n steps = 2^m steps 

et c'est pourquoi le coût est exponentiel.

Cela fonctionne beaucoup mieux:

 unsigned int Fib(unsigned int n) { // first Fibonaci number is Fib(0) // second one is Fib(1) and so on // unsigned int m; // m + current_n = original_n unsigned int a = 1; // Fib(m) unsigned int b = 0; // Fib(m-1) unsigned int c = 0; // Fib(m-2) while (n--) { c = b; b = a; a = b+c; } return a; }