如何减少斐波那契数列的运行时间（递归函数）

Question

n = 1
rep = 0

def f(n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        return f(n - 1) + f(n - 2)
     
while rep <= 50:
  print(f(n))
  rep += 1
  n += 1

我需要打印斐波那契数1~50

但是由于代码运行时间的原因会出现错误。

问。我该如何修复此代码以使其运行得更快？

问。应答代码将前一个数字 F(n-2) 移至临时函数，并将当前数字 F(n-1) 传送至前一个数字 F(n-2)；当斐波那契数排列在列表中时，这使得这两个数字后退一步。

（如有问题请忽略Q2）

Answer 1

请注意，您不需要递归：

a,b=0,1
print(a,b,end=' ')
for i in range(9):
  a,b=b,a+b
  print(b,end=' ')

Result:
0 1 1 2 3 5 8 13 21 34 55 

Answer 2

您需要保存所有已处理的数字，以便您的代码可以快速访问这些值。

你的代码正在做什么，对于一个数字

n

它是这样处理的。

f(n) = f(n-1) + f(n-2)
     = (f(n-2) + f(n-3)) + (f(n-3) + f(n-4))
     = ((f(n-3) + f(n-4)) + (f(n-4)+f(n-5))) + ((f(n-4) + f(n-5)) + (f(n-5)+f(n-6))

     .
     .
     . 
     so on

所以你可以看到，对于单个

n

，代码多次调用一些值。如果

n

更改为

n+1

，则再次遵循相同的过程。

因此为了克服这个问题，你需要保存每次调用的结果，以便我们可以在 O(1) 时间内得到结果。

您可以使用

lru_cache

（内置）或

dict

（使用自定义装饰器/函数）来保存每个斐波那契指数结果的值。

使用下面的

lru_cache

添加代码。

from functools import lru_cache
n = 1
rep = 0
@lru_cache
def f(n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        return f(n - 1) + f(n - 2)
     
while rep <= 50:
  print(f(n))
  rep += 1
  n += 1

Answer 3

long long int fib(int F[], int N[], int n, long long int *calls) {
if (N[n] == n) return F[n];
else if (n == 0 || n == 1) {
    F[n] = n; N[n] = n;
    return F[n];
}
else {
    N[n] = n; F[n] = fib(F, N, n - 2, calls) + fib(F, N, n - 1, calls);

}
return F[n]; }

您可以尝试这个基于两个数组的解决方案。 F[n] 用于存储 fib(n) 的结果，N[n] 用于存储 n