La complexité du calcul de la séquence de Fibonacci

StackOverflow https://stackoverflow.com/questions/360748

Question

Je comprends la notation Big-O, mais je ne sais pas comment le 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-il calculé?

Était-ce utile?

La solution

Vous modélisez la fonction de temps pour calculer comme somme Fib(n) temps de calcul plus le temps Fib(n-1) pour calculer plus le temps Fib(n-2) pour les ajouter ensemble (O(1)). Cela suppose que les évaluations répétées du même prendre la même T(n<=1) = O(1) temps -. Dire pas memoization est utilisé

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

n

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

Vous pouvez dessiner l'arbre de récursivité, qui aura la profondeur et comprendre intuitivement O(2 que cette fonction est asymptotiquement ) n = 1 T(n-1) = O(2. Vous pouvez ensuite prouver votre conjecture par induction.

Base est évident n-1

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

) + O(1) = O(2 qui est égale à

f(n) = f(n-1) + f(n-2) T(n) Fib(n) x O(1) θ(1.6 <=> <=> <=>

Cependant, comme il est indiqué dans un commentaire, ce n'est pas lié serré. Un fait intéressant sur cette fonction est que le T (n) est asymptotiquement le même en tant que valeur de <=> puisque les deux sont tels que définis

<=>.

Les feuilles de l'arbre de récursivité retourne toujours 1. La valeur de somme est de <=> toutes les valeurs renvoyées par les feuilles dans l'arbre de récursivité qui est égal au nombre de feuilles. Étant donné que chaque feuille prendra O (1) pour calculer, est égale à <=> <=>. Par conséquent, la limite serré pour cette fonction est la séquence de Fibonacci lui-même (~ <=> <=> <=>). Vous pouvez trouver cette borne étroite en utilisant des fonctions générant comme je l'avais mentionné ci-dessus.

Autres conseils

Il suffit de vous demander combien de déclarations doivent exécuter pour terminer à F(n).

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

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

Alors, quelle fonction remplit 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

pour Solve et vous obtenez (1+sqrt(5))/2 = 1.6180339887 <=>, autrement connu comme le .

Alors il faut du temps exponentielle.

Il y a une discussion très agréable de cette problème spécifique sur au MIT . A la page 5, ils font valoir que, si l'on suppose qu'une addition prend une unité de calcul, le temps nécessaire pour calculer Fib (N) est très étroitement liée au résultat de Fib (N).

Par conséquent, vous pouvez passer directement à l'approximation très proche de la série de Fibonacci: 

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

et dire donc que la plus mauvaise performance de cas 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 la fermée forme d'expression du nombre Nième Fibonacci plus sur Wikipedia si vous souhaitez plus d'informations.

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

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

D'abord, il est tout au sujet de déterminer combien de fois la fonction de fibonacci récursif (F () à partir de maintenant) est appelée lors du calcul du nombre Nième de fibonacci. Si elle est appelée une fois par numéro dans la séquence 0 à n, nous avons O (n), si elle est appelée n fois pour chaque numéro, puis nous obtenons O (n * n), ou O (n ^ 2), et ainsi de suite.

Alors, quand F () est appelée pour un nombre n, le nombre de fois F () est appelée pour un nombre donné entre 0 et n-1 pousse à l'approche 0.

En tant que première impression, il me semble que si nous d'une manière visuelle, en tirant une unité par unité de temps F () est appelée pour un nombre donné, humide obtenir une sorte de forme pyramidale (qui est, si nous centrer horizontalement unités). Quelque chose comme ceci: 

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

Maintenant, la question est, à quelle vitesse est la base de cette pyramide agrandissant que n croît?

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

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

Maintenant, nous voulons savoir combien de fois F (x) est appelé à tous, et nous pouvons voir le nombre de fois F (0) est appelé est seulement une partie.

Si nous déplaçons mentalement tous les * s de F (6) aux lignes F (2) dans F (1) ligne, nous voyons que F (1) et F (0) lignes sont maintenant égaux en longueur. Ce qui signifie, les temps totaux 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)

Vous pouvez développer 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(n-i)
     ...
     ==> O(2^n)

Il est délimité à l'extrémité inférieure par 2^(n/2) et sur l'extrémité supérieure par 2 ^ n (comme indiqué dans d'autres commentaires). Et un fait intéressant de cette mise en œuvre récursive est qu'il a un asymptotique serré lié de Fib (n) lui-même. Ces faits peuvent se résumer ainsi: 

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

La forme fermée étanche liée peut être réduite en utilisant davantage son si vous le souhaitez.

Les réponses sont bonnes preuve, mais je dois toujours faire quelques itérations à la main pour me convaincre vraiment. Alors je dessinais un petit appel arbre sur mon tableau blanc, et a commencé à compter les nœuds. Je partage mon compte sur des noeuds dans le total, nœuds feuilles et nœuds intérieurs. Voici ce que je suis: 

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

Que saute immédiatement est que le nombre de nœuds feuilles est fib(n). Ce qui a pris quelques itérations à noter 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 de calcul lors de la classification de la complexité, la réponse finale est θ(fib(n)).

La complexité temporelle de l'algorithme récursif peut être mieux estimée en traçant arbre de récursivité, Dans ce cas, la relation de récurrence pour le dessin arbre de récursivité serait T (n) = T (n-1) + T (n-2) + O (1 ) Notez que chaque étape prend O (1) signifie constante de temps, car il ne fait qu'une seule comparaison pour vérifier la valeur de n si arbre block.Recursion ressemblerait 

          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

permet de dire ici chaque niveau de l'arbre ci-dessus est désigné par i Par conséquent, 

i
0                        n
1            (n-1)                 (n-2)
2        (n-2)    (n-3)      (n-3)     (n-4)
3   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)

permet à dire valeur particulière de i, les extrémités des arbres, ce cas serait quand n-i = 1, d'où i = n-1, ce qui signifie que la hauteur de l'arbre est n-1. Maintenant nous allons voir à quel point le travail est fait pour chacune des n couches dans tree.Note que chaque étape prend O (1) le temps comme indiqué par rapport récurrence. 

2^0=1                        n
2^1=2            (n-1)                 (n-2)
2^2=4        (n-2)    (n-3)      (n-3)     (n-4)
2^3=8   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)    ..so on
2^i for ith level

depuis i = n-1 est la hauteur du travail de l'arbre fait à chaque niveau sera 

i work
1 2^1
2 2^2
3 2^3..so on

Par conséquent travail totale fait sera somme des travaux effectués à chaque niveau, d'où il sera 2 0 + ^ 2 ^ 1 + 2 + 2 ^ 2 ^ 3 ... + 2 ^ (n-1) étant donné que i = n -1. Par suite géométrique cette somme est 2 ^ n, d'où la complexité de la durée totale est ici O (2 ^ n)

Eh bien, selon moi, il est comme seul récursion O(2^n) prend le temps considérable dans cette fonction (diviser pour mieux régner). On voit que, la fonction ci-dessus continuera dans un arbre jusqu'à ce que les feuilles sont des approches quand nous arrivons au niveau F(n-(n-1)) à savoir F(1). Donc, ici quand on noter la complexité du temps rencontré à chaque profondeur de l'arbre, la série sommation est: 

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

qui est de l'ordre 2^n [ O(2^n) ].

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

A la racine vous calculez:

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

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

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

alors vous avez à chaque niveau 2 appels récursifs qui gaspillent beaucoup de données dans le calcul, la fonction de 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), alors

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

...

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

Ceci est juste une borne inférieure qui dans le but de votre analyse devrait être suffisant, mais la fonction en temps réel est un facteur d'une constante par la même formule et Fibonacci forme fermée est connu pour être exponentielle du nombre d'or.

De plus, vous pouvez trouver optimisé versions de Fibonacci en utilisant la programmation dynamique comme ceci: 

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];
}

optimisée et faire que n étapes, mais est aussi exponentielle.

Les fonctions coûts sont définies de la taille d'entrée au nombre d'étapes pour résoudre le problème. Quand vous voyez la version dynamique de Fibonacci ( n étapes pour calculer la table) ou le plus facile algorithme de savoir si un nombre est premier ( sqrt (n) pour analyser la validité diviseurs du nombre). vous pouvez penser que ces algorithmes sont O (n) ou O (sqrt (n)) , mais cela est tout simplement pas vrai pour la raison suivante: L'entrée de votre algorithme est un nombre n , en utilisant la notation binaire de la taille d'entrée pour un nombre entier n est log2 (n) faire ensuite un changement de variable de 

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

laisser savoir 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: 

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

et c'est la raison pour laquelle le coût est une exponentielle.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top