Propriétés de mauvais algorithme de fibonacci

Question

que je recherchais à l'algorithme mauvais fibonacci canonique l'autre jour:

public static int fib(int n) 
{ 
    // Base Case 
    if (n < 2) 
    return 1;  
    else 
    return fib(n-1) + fib(n-2);  
} 

J'ai fait l'observation intéressante. Lorsque vous appelez fib (n), alors pour k compris entre 1 et n fib (k) est appelé précisément fib (n-k + 1) fois (ou fib (n-k) selon votre définition de fib (0)). De plus, fib (0) est appelé fib (n-k-1) fois. Cela me permet alors de trouver que dans fib (100) il y a exactement 708449696358523830149 appels à la fonction fib.

Y a-t-il d'autres observations intéressantes sur cette fonction?

Note supplémentaire: Je connais tous les trucs sympas sur la mémorisation etc ... Je ne demande pas comment l'optimiser.

Answer 1

Ceci est un cas merveilleux pour lequel memoization est une optimisation très utile dans des fonctions telles que Fibonacci. Comme vous pouvez le voir, vous pouvez réduire le nombre d'appels de fonction de 2*fib(n)-1 à n - ce qui est de beaucoup mieux. En mathématiques, the Fibonacci numbers possède de nombreuses autres propriétés intéressantes.

Answer 2

Ajoutant à ce que Yuval a dit ...

En plus memoization, il est également intéressant de mentionner la étroitement liée « dynamic programming ». Très étroitement lié - Personnellement, je ne sais pas trop si la mémoisation est un cas particulier de programmation dynamique ou non. Quoi qu'il en soit, dans ce cas, la solution itérative standard pourrait être appelée une solution de programmation dynamique.

Dans la solution itérative, lorsque vous essayez de calculer fib(n), vous avez déjà calculé les solutions partielles fib(n-2) et fib(n-1) si vous venez de réutilisation de ces solutions partielles précalculées. Que cela se fasse en boucle n'est pas important pour la programmation dynamique. La mémorisation peut être un cas particulier (je ne suis pas sûr que ce soit toujours un cas particulier selon des définitions strictes). Le point clé est que chaque solution partielle est mémorisée, de sorte qu'elle n'a besoin d'être calculée qu'une seule fois.

Answer 3

Je vais juste jeter cette note plus mathématique. La grande notation O pour votre algorithme est en effet F (n), mais qu'est-ce que cela signifie par rapport à O (N^2) ou O (NlogN) nous normalement penser?

Son mauvais fou: il a O (e^N) espace et temps complexité. Mathématiquement, vous pouvez montrer que lim (N-> \ inf) F (n) = ((1+ \ sqrt (5))/2)^N