La complexité algorithmique de la suite de Fibonacci

Je comprends Big-O de la notation, mais je ne sais pas comment le calculer pour de nombreuses fonctions. En particulier, j'ai été à essayer de comprendre la complexité de calcul de la version naïve de la suite de Fibonacci:

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

Qu'est-ce que la complexité de calcul de la suite de Fibonacci et comment est-il calculé?

  • les Bonnes réponses ici.
  • Voir la matrice de la forme de l'article ici: en.wikipedia.org/wiki/Fibonacci_number . en procédant de cette matrice ^ n (dans une manière intelligente de), vous pouvez calculer Fib(n) en temps O(lg n). Le truc, c'est de faire la fonction de puissance. Theres une très bonne conférence sur iTunesU à propos de ce problème et comment le résoudre en temps O(lg n). Le cours d'intro à des algorithmes de MIT conférence 3 (son absolument libre de sorte de vérifier si vous êtes intéressés)
  • Ni des commentaires ci-dessus l'adresse de la question, qui est de parler de la complexité de calcul de la version naïve (posté dans le code), pas plus intelligent versions comme la matrice de la forme ou de la non-récursive de calcul.
  • Une très belle vidéo ici qui parle à la fois de la limite inférieure de la complexité(2^n/2) et la limite supérieure de la complexité(2^n) de récursive de la mise en œuvre.
  • Une note de la requête: la naïfs la mise en œuvre de la suite de Fibonacci être itératif ou récursive?
InformationsquelleAutor Juliet | 2008-12-11
  1. 335

    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 calculer Fib(n-2) plus le temps d'ajouter de l'ensemble (O(1)). C'est en supposant que les évaluations de la même Fib(n) prendre le même temps - c'est à dire pas de memoization est utiliser.

    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

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

    T(n) = T(n-1) + T(n-2) + O(1) 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 au comme 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.

    • Aussi la Preuve par induction. Nice. +1
    • Bien que la limite n'est pas serré.
    • Erreur De Segmentation: Oui. J'ai clarifié la réponse. Vous obtiendrez le serré lié à l'aide de GF méthode que j'avais écrit ci-dessus.
    • Itake votre StackOverflowException comme une blague. Le temps exponentiel est perceptible assez facilement avec d'assez petites valeurs de n.
    • pouvez-vous expliquer pourquoi prendre u T(n-1) = O(2^n-1). T(n-1) (n^2), en raison de Fibonacci ont des appels T(n-1)+T(n-2) donc, après additionnant tous les coûts (2*2*2....) devrait être de 2^n.
    • Est la preuve par induction vraiment correcte? Il semble que vous pourriez tout aussi simplement supposer que T(n) = O(n) et alors que vous auriez T(n) = O(n-1) + O(n-2) + O(1) = O(n) donc T(n) = O(n) mais qui n'est évidemment pas vrai? Si elle est correcte, s'il vous plaît expliquer..
    • La logique utilisée ici n'est pas précis, l'hypothèse d'induction est trop faible, car il comprend déjà le big-O à l'intérieur. La bonne hypothèse est-à-dire que T(n) <= c*2^n pour certains c, puis à partir de la conclusion de la preuve inductive, vous pouvez en déduire que T(n) = O(2^n)
    • Cette preuve est mauvais, mais il est proche. L'hypothèse ici est trop faible. L'hypothèse états T(n-1) = O(2^(n-1)), mais PAS que T(n-2) = O(2^(n-2)) qui Mehrdad utilise dans la dernière étape de la preuve. Nous ne savons pas T(n-2) = O(2^(n-2)). La solution la plus simple pour cela est d'utiliser l'induction, plutôt que partielle. Montrer l'énoncé est vrai pour Fib n ° 1 et Fib#2, alors vous pouvez supposer T(n-2) = O(2^(n-2)), et la preuve en est titulaire.

    InformationsquelleAutor
  2. 116

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

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

    Diviser par un(n-2):

    un2 == un + 1

    Résoudre pour a et vous obtenez (1+sqrt(5))/2 = 1.6180339887, autrement connu comme l' nombre d'or.

    Donc ça prend du temps exponentiel.

    • La preuve par induction. Nice. +1
    • 30 upvotes pour une mauvaise réponse? 🙂 Est-ce que 1=F(1)=(1+sqrt(5))/2 ? Et que dire de l'autre solution, (1-sqrt(5))/2?
    • Non, 1 n'est pas égal à 1 + 1. La fonction qui satisifes ces règles est mentionné dans la question.
    • La réponse n'est pas faux. C'est juste asymptomatiques. L'autre solution est négative n'est pas physiquement sens.
    • Quelqu'un peut m'expliquer comment un^n == a^(n-1) + a^(n-2) satisfaire à ces règles? Comment est-il satisfait exactement, veuillez être précis.
    • Rappelez-vous que la complexité du temps de n'importe quel arbre est O(no_of_branches ^ depth_of_tree)? Pour n'importe quelle branche de la fib(N), étant donné que ce n'est pas un arbre parfait au fond, en fin de compte, la hauteur est N, mais le "nombre moyen de branches" est un peu moins de 2. Donc, pour obtenir le nombre exact x, nous supposons pour n'importe quelle branche de la fib(n), le O(n) est x^n. Ainsi x^n = x^n-1 + x^n-2.

    InformationsquelleAutor Jason Cohen
  3. 29

    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 de dire, donc, 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 fermé forme d'expression de la n-ième nombre de Fibonacci sur Wikipedia si vous souhaitez plus d'informations.

    • Merci pour le cours lien. Très belle observation de trop
    InformationsquelleAutor Bob Cross
  4. 29

    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.

    D'abord, il s'agit de déterminer combien 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)
    • F(3) ne reçoit appelé 3 fois et pas 4 fois. La deuxième pyramide est faux.
    • F(3) = 3, F(2) = 5, F(1) = 8, F(0) = 5. Je voudrais corriger, mais je ne pense pas que je peux sauver cette réponse avec une modification.
    InformationsquelleAutor J.P.
  5. 15

    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)
    • Je comprends la première ligne. Mais pourquoi est-il moins de caractère < à la fin? Comment avez-vous T(n-1) + T(n-1)?
    • c'est une flèche. -> [(pas moins). Désolé pour la confusion au sujet de la dernière ligne]. Pour la première ligne, bien... T(n-1) > T(n-2) je peux Donc changer T(n-2) et mettre T(n-1). Je ne obtenir une limite supérieure qui est toujours valable pour T(n-1) + T(n-2)
    InformationsquelleAutor Tony Tannous
  6. 9

    Il est 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 récursive de la mise en œuvre, c'est qu'il a un serré asymptotique 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)

    Le resserrement lié peut être réduite à l'aide de son forme fermée si vous le souhaitez.

    InformationsquelleAutor Dave L.
  7. 9

    La preuve réponses sont bonnes, mais je dois toujours faire un peu d'itérations à la main pour vraiment me convaincre. Donc, j'ai fait un petit appel de l'arbre sur mon tableau blanc, et a commencé à compter les nœuds. J'ai divisé mon compte dans le total des nœuds, les nœuds feuilles, et de l'intérieur des nœuds. Voici 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 remarquer que le nombre de nœuds feuilles est fib(n). Ce qui a eu un peu plus d'itérations pour avis 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 la classification complexité de calcul, la réponse finale est θ(fib(n)).

    • (Non, je n'ai pas dessiner un plein de 10 profondeur de l'arbre d'appel sur mon tableau blanc. Juste à 5 de profondeur.) 😉
    • Nice, je me demandais comment beaucoup d'additions supplémentaires récursive Fib fait. Ce n'est pas seulement l'ajout de 1 à un seul accumulateur Fib(n) fois, mais intéressant de noter que c'est toujours exactement θ(Fib(n)).
    • Notez que certains (la plupart) récursive implémentations de passer du temps en ajoutant 0, cependant: la récursivité de la base de cas sont 0 et 1, parce qu'ils ne Fib(n-1) + Fib(n-2). Alors, probablement, le 3 * Fib(n) - 2 à partir de ce lien seule réponse est plus précis pour le nombre total de nœuds, pas 2 * Fib(n) - 1.
    InformationsquelleAutor benkc
  8. 6

    Récursive de l'algorithme de complexité temporelle peut être mieux évalué par le dessin de la récursivité de l'arbre, Dans ce cas, la relation de récurrence pour le dessin de la récursivité arbre serait T(n)=T(n-1)+T(n-2)+O(1)
    notez que chaque étape prend O(1) la signification de la constante de temps,car il ne fait qu'une comparaison de vérifier la valeur de n dans si bloc.La récursivité de l'arbre ressemblerait

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

    Ici permet de dire que chaque niveau d'au-dessus de l'arbre est désigné par je
    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 de dire à la valeur de i, l'arbre se termine, ce cas serait le cas de la n-i=1, donc i=n-1, ce qui signifie que la hauteur de l'arbre est n-1.
    Maintenant essayons de voir comment beaucoup de travail est fait pour chacun des n couches dans l'arbre.Notez que chaque étape prend O(1) dans la relation de 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 de l'arbre le travail effectué à chaque niveau sera

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

    Donc total sera la somme de travail effectué à chaque niveau, par conséquent, il sera 2^0+2^1+2^2+2^3...+2^(n-1) i=n-1.
    Par série géométrique de cette somme est de 2^n, et par conséquent le temps total complexité est ici O(2^n)

    InformationsquelleAutor nikhil kekan
  9. 2

    Bien, selon moi, c'est O(2^n) dans cette fonction uniquement de la récursivité, c'est prendre le temps considérable (diviser pour régner). Nous voyons que la fonction ci-dessus continuera dans un arbre jusqu'à ce que les feuilles sont des approches lorsque nous atteignons le niveau F(n-(n-1)) c'est à dire F(1). Donc, ici, quand nous avons de noter le temps de la complexité rencontrées à chaque profondeur de l'arbre, la somme de la série est:

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

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

    InformationsquelleAutor pgaur
  10. 0

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

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

    • Il est aussi agréable si vous pouviez expliquer votre réponse, plutôt que de poster un lien.
    • Aucune explication n'est fournie
    InformationsquelleAutor nsh3
  11. 0

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

    À la racine vous êtes informatique:

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

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

    F(n-2) dépend de F(n-3) 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 C constante

    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 le but de votre analyse devrait être suffisant, mais le temps réel de la fonction est un facteur d'une constante par la même formule de Fibonacci et le forme fermée est connu pour être exponentielle du nombre d'or.

    En outre, vous pouvez trouver des versions optimisées de Fibonacci à l'aide de 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 de ne faire que n étapes, mais est aussi exponentielle.

    Les fonctions de coût sont définis à partir d'une Entrée de taille pour le nombre d'étapes pour résoudre le problème. Quand vous voyez la version dynamique de Fibonacci (n étapes pour calculer la table) ou la méthode la plus simple de l'algorithme de savoir si un nombre est premier (sqrt(n) pour analyser la validité de diviseurs 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:
    Le signal d'entrée de l'algorithme est un nombre: n, à l'aide de la notation binaire la taille de saisie pour un entier n est log2(n) puis en 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

    ensuite le coût de votre algorithme en fonction de la taille de saisie est:

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

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

    InformationsquelleAutor Miguel
  12. -4

    Effectue cette manière de 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;
}
    • Cela n'explique pas comment calculer big O la notation de la fonction.
    • Ellen: C'est simple. Cette fonction est O(n), puisque le nombre d'itérations de la while boucle est égale à n, et il n'y a pas d'autre boucle ou d'un appel récursif. (Prouvant 6*n + 4 est O(n) est trivial si vous connaissez la définition de la O notation.)
    • La détermination de Big-O est entièrement académique, sauf si vous avez une alternative de mise en œuvre (et Big-O) pour la comparer. Eduardo fournit le contrepoint ici.
    • Je suis d'accord que cela peut être une bien meilleure façon de la mettre en œuvre, mais la notion de Big-O commentaires sur l'algorithme utilisé pour un problème. Par exemple, le moteur d'exécution de bogosort (en.wikipedia.org/wiki/Bogosort) est O(2^n), mais il y a d'autres façons de trier une liste plus efficacement (par exemple tri de la sélection). Je pense que Juliette se pose au sujet de l'ordre de l'algorithme, elle a fourni, qu'elle appelle la "version naïve."
    • D'accord. Depuis son algorithme ajoute juste 1s, l'ordre de son algorithme est O(Fib(n)) lui-même.
    • pas à la bonne place
    • Ne pas répondre à la question. Il n'a pas demandé une meilleure mise en œuvre, il a demandé la complexité algorithmique de son propre.

    InformationsquelleAutor pyon