为什么递归斐波那契方法的时间数据中存在斐波那契模式？

Question

我在 class 关于动态编程与递归讲座的演讲中第一次注意到这种模式。在第 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

现在，让我们输入一些实数来更好地证明这一点。

让我们假设如下：

n = 10

f(9) takes 5 seconds to calculate

f(8) takes 3 seconds to calculate

在这种情况下：

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

其他一些注意事项:

*实际运行的时间并不总是与预期模式一样精确。如果您查看以下输出，甚至可以从您的数据中看出这一点：

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) 调用中完成。

*在达到某个斐波那契数之前，可能看不到该模式。这将取决于您的时间测量精度。例如，如果您以秒为单位进行测量，并且只精确到小数点后一位（即十分之一秒），那么在您通过 0.0 秒配置文件之前，模式不会出现。

为什么递归斐波那契方法的时间数据中存在斐波那契模式？

Why is there a Fibonacci pattern in the timing data for a recursive Fibonacci method?

recursion

timing

fibonacci