Pourquoi y a-t-il un patron de Fibonacci dans les données de synchronisation pour une méthode récursive de Fibonacci?

Question

J'ai d'abord remarqué ce modèle dans ma présentation de classe par rapport à la programmation de la programmation dynamique par rapport à la récurrence. Aux environs du 7ème numéro de Fibonacci, on voit le motif de Fibonacci. Y a-t-il une explication à cela?

The lecture presentation can be found here:

j'ai décidé de reproduire les données et remarquées le modèle aussi bien. Voici mon code pour mon expérience:

import time 

def fib(n): 
    if(n <= 2): 
     return 1 
    else: 
     return fib(n - 1) + fib(n - 2) 

for i in range(0, 100): 
    start = time.time() 
    print "fib(", i,") = ", fib(i), " with time: ", time.time() - start 

data

Answer 1

La raison pour laquelle cela se produit est due aux appels récursifs dans la récurrence de fibonacci.

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

Supposons que les éléments suivants:

f(n-1) takes X seconds to calculate 

f(n-2) takes Y seconds to calculate. 

Therefore, f(n) will take X + Y seconds to calculate since f(n) = f(n-1) + f(n-2) 

Maintenant, si l'on considère les prochains numéros de fibonacci:

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

f(n+1) will take X + Y seconds + X seconds = 2X + Y seconds 

// f(n+2) = f(n+1) + f(n) 
f(n+2) will take 2X + Y + X + Y seconds = 3X + 2Y seconds 

Maintenant, nous allons mettre dans un certain nombre réel pour mieux démontrer.

Supposons que les éléments suivants:

n = 10 

f(9) takes 5 seconds to calculate 

f(8) takes 3 seconds to calculate 

Dans ce cas:

f(10) will take 5 + 3 = 8 seconds to calculate 

f(11) will take 5 + 3 + 5 = 2(5) + 3 = 13 seconds to calculate 

f(12) will take 2(5) + 3 + 5 + 3 = 3(5) + 2(3) = 21 seconds to calculate 

Quelques autres choses à noter:

* Les temps de parcours réels ne seront pas toujours aussi précis comme le modèle attendu. Cela peut même être vu de vos données si vous regardez la sortie suivante:

fib(43) = 433494437 with time: 62.495429039 
fib(44) = 701408733 with time: 101.303709984 
fib(45) = 1134903170 with time: 161.135010004 

161,135010004 est inférieur (62,495429039 + 101,303709984)

Cela peut être dû FIB (43) en cours d'exécution un peu plus rapide dans le fib (45) appel, alors il l'a fait dans l'appel fib (44).

* Le motif peut ne pas être visible avant d'avoir atteint un certain nombre de fibonnaci. Cela dépendra de la précision de votre mesure du temps. Par exemple, si vous mesurez en secondes et que vous ne faites que passer à une décimale (c'est-à-dire 10 secondes de seconde), le motif ne sortira pas tant que vous n'aurez pas passé les profils de 0,0 seconde.