Complexité informatique 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 à calculer Fib(n)comme la somme du temps à calculer Fib(n-1)plus le temps à calculer Fib(n-2)plus le temps de les additionner ( O(1)). Cela suppose que des évaluations répétées du même Fib(n)prennent le même temps - c'est-à-dire qu'aucune mémorisation n'est utilisée.

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 vous retrouverez avec la réponse.

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

Base: n = 1est évident

Supposons , par conséquentT(n-1) = O(2n-1)

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

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

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

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

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

Demandez-vous simplement combien d'instructions doivent F(n)être exécutées pour terminer.

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

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

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

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

Divisez par un ^(n-2) :

a ² == a + 1

Résolvez aet vous obtenez (1+sqrt(5))/2 = 1.6180339887, autrement connu comme le nombre d' or .

Cela prend donc un temps exponentiel.

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

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

Tout d'abord, il s'agit de déterminer combien de fois la fonction fibonacci récursive (F () à partir de maintenant) est appelée lors du calcul du nombre Nth fibonacci. S'il est appelé une fois par nombre 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é 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, en dessinant une unité par temps F () est appelé pour un nombre donné, humide obtenir une sorte de forme pyramidale (c'est-à-dire, si nous centrons 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

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

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 de longueur égale. Ce qui signifie que le nombre total de fois où 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)

Il y a une très belle discussion sur ce problème spécifique au MIT . À la page 5, ils indiquent que, si vous supposez qu'un ajout prend une unité de calcul, le temps requis 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 pire 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 sous forme fermée du nombre Nth Fibonacci sur Wikipedia si vous souhaitez plus d'informations.

Vous pouvez l'étendre et avoir une visulisation

     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 à 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 étroite de Fib (n) elle-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)

Le lien serré peut être encore réduit en utilisant sa forme fermée si vous le souhaitez.

Les preuves 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 commencé à compter les nœuds. J'ai divisé mes comptes en nœuds totaux, nœuds feuilles et nœuds intérieurs. Voici ce que j'ai obtenu:

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 aux yeux, c'est que le nombre de nœuds foliaires est fib(n). Ce qui a pris quelques itérations de plus à remarquer, 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 supprimez les coefficients lors de la classification de la complexité de calcul, la réponse finale est θ(fib(n)).

La complexité temporelle de l'algorithme récursif peut être mieux estimée en dessinant un arbre de récursivité. Dans ce cas, la relation de récurrence pour dessiner un arbre de récursivité serait T (n) = T (n-1) + T (n-2) + O (1) notez que chaque étape prend O (1), ce qui signifie un temps constant, car il ne fait qu'une seule comparaison pour vérifier la valeur de n dans le bloc if .

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

Ici, disons que chaque niveau de l'arbre ci-dessus est noté i donc,

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)

disons à une valeur particulière de i, l'arbre se termine, ce cas serait lorsque ni = 1, donc i = n-1, ce qui signifie que la hauteur de l'arbre est n-1. Voyons maintenant combien de travail est effectué pour chacune des n couches dans l'arbre.Notez que chaque étape prend O (1) comme indiqué 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

puisque 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

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

Eh bien, selon moi, c'est O(2^n)que dans cette fonction, seule la récursivité prend beaucoup de temps (diviser pour mieux régner). Nous voyons que la fonction ci-dessus continuera dans un arbre jusqu'à ce que les feuilles approchent lorsque nous atteignons le niveau F(n-(n-1))ie F(1). Donc, ici, quand nous notons la complexité temporelle rencontrée à chaque profondeur d'arbre, la série de sommations est:

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

c'est l'ordre du 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:

À la racine, 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 de F (n-3)

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

alors vous avez à chaque niveau 2 des 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 qui, aux fins de votre analyse, devrait être suffisante, mais la fonction en temps réel est un facteur d'une constante par la même formule de Fibonacci et la forme fermée est connue pour être exponentielle du nombre d'or.

De plus, vous pouvez trouver des versions optimisées de Fibonacci en utilisant une programmation dynamique 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 étapes mais est également exponentiel.

Les fonctions de coût sont définies de la taille d'entrée au nombre d'étapes pour résoudre le problème. Lorsque vous voyez la version dynamique de Fibonacci ( n étapes pour calculer la table) ou l'algorithme le plus simple pour 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) faisant alors un changement variable de

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

permet de connaître 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 pourquoi le coût est exponentiel.

Il est simple à calculer en schématisant les appels de fonction. Ajoutez simplement les appels de fonction pour chaque valeur de n et regardez comment le nombre augmente.

Le Big O est O (Z ^ n) où Z est le nombre d'or ou environ 1,62.

Les nombres de Leonardo et les nombres de Fibonacci approchent ce rapport lorsque nous augmentons n.

Contrairement à d'autres questions Big O, il n'y a pas de variabilité dans l'entrée et l'algorithme et la mise en œuvre de l'algorithme sont clairement définis.

Il n'y a pas besoin d'un tas de mathématiques complexes. Diagrammez simplement les appels de fonction ci-dessous et ajustez une fonction aux nombres.

Ou si vous connaissez le nombre d'or, vous le reconnaîtrez comme tel.

Cette réponse est plus correcte que la réponse acceptée qui prétend qu'elle approchera f (n) = 2 ^ n. Ça ne le sera jamais. Il approchera f (n) = golden_ratio ^ n.

2 (2 -> 1, 0)

4 (3 -> 2, 1) (2 -> 1, 0)

8 (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)


14 (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)

            (3 -> 2, 1) (2 -> 1, 0)

22 (6 -> 5, 4)
            (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

                        (3 -> 2, 1) (2 -> 1, 0)

            (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

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

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