재귀 피보나치 방법의 타이밍 데이터에 피보나치 패턴이있는 이유는 무엇입니까?

Question

먼저 동적 프로그래밍 대 재귀 강의보다 내 수업 프레젠테이션에서이 패턴을 발견했습니다. 7 번째 피보나치 수 부근에서 피보나치 패턴이 보입니다. 이것에 대한 설명이 있습니까?

The lecture presentation can be found here:

은 내가 데이터를 재생하기로 결정뿐만 아니라 패턴을 발견했습니다.

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

이 일어나고있는 이유는 피보나치 재발 내에서 재귀 호출로 인해 : 여기 내 실험에 대한 내 코드입니다.

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

은의 다음을 가정 해 봅시다 :

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) 

을 이제 우리는 다음 몇 피보나치 수를 고려하는 경우 :

이제

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 

,의 더 나은이를 입증하기 위해 몇 가지 실수에 넣어 보자. 실제 실행은 항상 정확하지 않습니다에서

* 시간 :

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 

몇 가지 다른 일을을 참고 :이 경우

n = 10 

f(9) takes 5 seconds to calculate 

f(8) takes 3 seconds to calculate 

:

의 다음을 가정 해 봅시다 예상 된 패턴으로.

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

161.135010004이 (62.495429039 + 101.303709984)

이 가능 인해 FIB (43)이 될 수 이하가 약간 빨라입니다 : 당신은 다음과 같은 결과를 보면 이것도 데이터에서 볼 수있다 fib (45) 호출을 호출하면 fib (44) 호출에서 수행됩니다.

* 특정 fibonnaci 번호가 나타날 때까지 패턴이 표시되지 않을 수 있습니다. 이것은 시간 측정의 정밀도에 달려 있습니다. 예를 들어, 몇 초 만에 측정하고 소수점 한 자리 (즉, 10 분의 1 초)로 이동하는 경우, 0.0 초 프로파일을 통과 할 때까지 패턴이 표시되지 않습니다.