Complexité computationnelle de la séquence de Fibonacci

il suffit de se demander combien d'instructions doivent être exécutées pour F(n) à compléter.

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 ⁿ (a > 1):

un ⁿ = = ^(n-1) + un ^(n-2)

diviser par un ^(n-2) :

un ² == un + 1

résoudre pour a et vous obtenez (1+sqrt(5))/2 = 1.6180339887 , autrement connu sous le ratio d'or .

donc ça prend un temps exponentiel.

il y a une très belle discussion de ce problème spécifique au MIT . À la page 5, ils font remarquer que, si vous présumez qu'une addition prend une unité de calcul, le temps requis pour calculer Fib(N) est très étroitement lié 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, par conséquent, que le pire des cas la performance 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 en forme fermée du nième numéro Fibonacci plus à Wikipedia si vous souhaitez plus d'information.

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

j'en suis arrivé à la même conclusion par un raisonnement plutôt simpliste mais je crois toujours valable.

tout d'abord, il s'agit de comprendre combien de fois la fonction fibonacci récursive ( F() à partir de maintenant ) est appelée lors du calcul du niè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), si elle est appelée n fois pour chaque nombre, alors on obtient O(n*n) ou O(n^2), et ainsi de suite.

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

comme première impression, il me semble que si nous le mettons de manière visuelle, dessiner une unité par temps F() est appelé pour un nombre donné, humide obtenir une sorte de forme de pyramide (c'est-à-dire, si nous centrons les unités horizontalement). Quelque chose comme ceci:

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

maintenant, la question est, à quelle vitesse la base de cette pyramide s'agrandit-elle au fur et à 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

nous voyons F (0) est appelé 32 fois, qui est 2^5, qui pour ce cas d'échantillon est 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 toutes les lignes *de F(6) à F(2) dans la ligne F(1), on voit que les lignes F(1) et F(0) sont maintenant égales en longueur. Ce qui signifie, total times F() est appelé quand 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 un visulization

     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é sur le bas, 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 implémentation récursive est qu'elle a une limite asymptotique serrée de Fib(n) elle-même. Ces faits peuvent être résumés comme suit:

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

la limite étanche peut être encore réduite en utilisant son forme fermée si vous voulez.

les réponses de preuve sont bonnes, mais je dois toujours faire quelques itérations à la main pour vraiment me convaincre. Alors j'ai dessiné un petit arbre d'appel sur mon tableau blanc, et j'ai commencé à compter les noeuds. J'ai divisé mes comptes dehors en noeuds totaux, les noeuds de feuille, et les noeuds intérieurs. Voilà ce que j'ai:

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 saute immédiatement, c'est que le nombre de noeuds foliaires est fib(n) . Ce qui a pris quelques itérations supplémentaires à noter est que le nombre de noeuds intérieurs est fib(n) - 1 . Par conséquent, le nombre total de noeuds est 2 * fib(n) - 1 .

puisque vous laissez tomber les coefficients lors de la classification de la complexité computationnelle, la réponse finale est θ(fib(n)) .

Eh bien, selon moi, il est O(2^n) comme dans cette fonction seule la récursion prend le temps considérable (diviser pour mieux régner). Nous voyons que, la fonction ci-dessus continuera dans un arbre jusqu'à ce que les feuilles sont approches lorsque nous atteignons le niveau F(n-(n-1)) c.-à-d. F(1) . Donc, ici, quand on note la complexité temporelle rencontrée à chaque profondeur de l'arbre, la série de sommation est:

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

c'est-à-dire l'ordre de 2^n [ O(2^n) ] .

http://www.ics.uci.edu/~eppstein/161/960109.html

de temps(n) = 3F(n) - 2

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

à 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) de nouveau et F (N-3)

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

, alors vous êtes d'avoir à 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 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))

c'est juste une limite inférieure que pour les besoins de votre analyse devrait être suffisant, mais la fonction temps réel est un facteur d'une constante par le même La formule de Fibonacci et la forme fermée est connue pour être exponentielle du rapport d'or.

en outre, vous pouvez trouver des versions optimisées 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];
}

qui est optimisé et ne fait que des pas n mais est aussi exponentielle.

les fonctions de coût 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 l'algorithme le plus facile à savoir si un nombre est premier ( sqrt (n) pour analyser les diviseurs valides du nombre). vous pouvez penser que ces algorithmes sont O(n) ou O(sqrt(n)) mais ce n'est tout simplement pas vrai pour la raison suivante: L'entrée de votre algorithme est un nombre: n , en utilisant la notation binaire la taille d'entrée pour un entier n est log2 (n) alors faisant un changement de variable de

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

laissez savoir que le nombre d'étapes en fonction de la taille de saisie

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 pourquoi le coût est exponentiel.

effectue une façon 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;
}