斐波那契数列生成算法的优化

Question

众所周知，生成斐波那契数列的最简单算法如下：

if(n<=0) return 0;
else if(n==1) return 1;
f(n) = f(n-1) + f(n-2);

但是这个算法有一些重复的计算。例如，如果你计算f(5)，它将计算f(4)和f(3)。当你计算f(4)时，它将再次计算f(3)和f(2)。有没有更加时间高效的递归算法呢？

- chaonextdoor

---

f(n - 1) = f(n - 2) + f(n - 3) 所以 f(n) = 2 * f(n - 2) + f(n - 3)。你可以缓存 f(n - 2)。当然，如果你选择的编程语言有 yield，那么迭代实现会更好。 - Ry-

@minitech 如果我想使用缓存方法，你能给我完整的代码吗？ - chaonextdoor

@minitech 你对 JavaScript 没有意见吧？ - chaonextdoor

Answer 1

我已经了解了一些计算斐波那契数列的时间复杂度高效的方法，以下是其中一些——

方法1-动态规划 现在这里的子结构通常是已知的，因此我将直接跳到解决方案——

static int fib(int n) 
{ 
int f[] = new int[n+2]; // 1 extra to handle case, n = 0 
int i; 

f[0] = 0; 
f[1] = 1; 

for (i = 2; i <= n; i++) 
{ 
    f[i] = f[i-1] + f[i-2]; 
} 

return f[n]; 
}

以下是更加节省空间的实现方法 -

static int fib(int n) 
 { 
    int a = 0, b = 1, c; 
    if (n == 0) 
        return a; 
    for (int i = 2; i <= n; i++) 
    { 
        c = a + b; 
        a = b; 
        b = c; 
    } 
    return b; 
} 

方法2-（使用矩阵{{1,1},{1,0}}的幂）

这是一种O(n)的算法，它依赖于这样一个事实：如果我们将矩阵M={{1, 1}, {1, 0}}自乘n次（换句话说，计算power(M,n)），那么我们可以得到第(n+1)个斐波那契数作为结果矩阵中行和列(0,0)处的元素。该解决方案需要O(n)时间。

矩阵表示法给出了以下闭合表达式的斐波那契数： fibonaccimatrix

static int fib(int n) 
{ 
int F[][] = new int[][]{{1,1},{1,0}}; 
if (n == 0) 
    return 0; 
power(F, n-1); 

return F[0][0]; 
} 

/*multiplies 2 matrices F and M of size 2*2, and 
puts the multiplication result back to F[][] */
static void multiply(int F[][], int M[][]) 
{ 
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; 

F[0][0] = x; 
F[0][1] = y; 
F[1][0] = z; 
F[1][1] = w; 
} 

/*function that calculates F[][] raise to the power n and puts the 
result in F[][]*/
static void power(int F[][], int n) 
{ 
int i; 
int M[][] = new int[][]{{1,1},{1,0}}; 

// n - 1 times multiply the matrix to {{1,0},{0,1}} 
for (i = 2; i <= n; i++) 
    multiply(F, M); 
} 

这可以通过优化，使时间复杂度为O(Logn)。我们可以使用递归乘法在先前的方法中计算power(M, n)。

static int fib(int n) 
{ 
int F[][] = new int[][]{{1,1},{1,0}}; 
if (n == 0) 
    return 0; 
power(F, n-1); 

return F[0][0]; 
} 

static void multiply(int F[][], int M[][]) 
{ 
int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1]; 

F[0][0] = x; 
F[0][1] = y; 
F[1][0] = z; 
F[1][1] = w; 
} 

static void power(int F[][], int n) 
{ 
if( n == 0 || n == 1) 
  return; 
int M[][] = new int[][]{{1,1},{1,0}}; 

power(F, n/2); 
multiply(F, F); 

if (n%2 != 0) 
   multiply(F, M); 
} 

方法3（O(log n)时间复杂度） 下面是另一个有趣的递推公式，可以用来在O(log n)的时间内找到第n个斐波那契数。

如果n是偶数，则k = n/2： F(n) = [2*F(k-1) + F(k)]*F(k)

如果n是奇数，则k = (n+1)/2： F(n) = F(k)*F(k) + F(k-1)*F(k-1) 这个公式是如何工作的呢？ 可以从上面的矩阵方程中推导出该公式。 fibonaccimatrix

对两边取行列式，得到 (-1)n = Fn+1Fn-1 – Fn2 并且，由于对于任意方阵A，AnAm = An+m，因此可以推出以下恒等式（它们是从矩阵乘积的两个不同系数中得到的）

FmFn + Fm-1Fn-1 = Fm+n-1

通过将n = n+1代入上式，得到

FmFn+1 + Fm-1Fn = Fm+n

将m = n代入上式，得到

F2n-1 = Fn2 + Fn-12

F2n = (Fn-1 + Fn+1)Fn = (2Fn-1 + Fn)Fn（来源：维基百科）

为了得到要证明的公式，我们只需要按照以下步骤进行即可： 如果n是偶数，我们可以令k = n/2 如果n是奇数，我们可以令k = (n+1)/2

public static int fib(int n) 
{ 

    if (n == 0) 
        return 0; 

    if (n == 1 || n == 2) 
        return (f[n] = 1); 

    // If fib(n) is already computed 
    if (f[n] != 0) 
        return f[n]; 

    int k = (n & 1) == 1? (n + 1) / 2 
                        : n / 2; 

    // Applyting above formula [See value 
    // n&1 is 1 if n is odd, else 0. 
    f[n] = (n & 1) == 1? (fib(k) * fib(k) +  
                    fib(k - 1) * fib(k - 1)) 
                   : (2 * fib(k - 1) + fib(k))  
                   * fib(k); 

    return f[n]; 
} 

方法四 - 使用公式 在此方法中，我们直接实现斐波那契数列的第n项公式。时间复杂度O(1)，空间复杂度O(1)。 Fn = {[(√5 + 1)/2] ^ n} / √5

static int fib(int n) { 
double phi = (1 + Math.sqrt(5)) / 2; 
return (int) Math.round(Math.pow(phi, n)  
                    / Math.sqrt(5)); 
} 

参考文献: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html

该网址提供了关于斐波那契数列的公式和相关信息。

- thealchemist

Answer 2

查看用Erlang实现的内容，它使用公式：。它表现出良好的线性结果行为，因为在 O(M(n) log n) 的一部分中，对于大数，M(n) 是指数级的。它可以在 2 秒内计算出具有 208988 位数字的一百万斐波那契数。诀窍在于，您可以使用（尾递归）公式（尾部意味着具有 O(1) 的空间，当使用适当的编译器或重写为循环时），在 O(log n) 个乘法中计算出幂：

% compute X^N
power(X, N) when is_integer(N), N >= 0 ->
    power(N, X, 1).

power(0, _, Acc) ->
    Acc;
power(N, X, Acc) ->
    if N rem 2 =:= 1 ->
            power(N - 1,   X,     Acc * X);
        true ->
            power(N div 2, X * X, Acc)
    end.

在这里，您需要用矩阵替换 X 和 Acc。 X 将被初始化为 ，而 Acc 则是等于恒等矩阵 I，即 。

- Hynek -Pichi- Vychodil

Answer 3

一种简单的方式是迭代计算而不是递归计算。这样可以在线性时间内计算出F(n)。

def fib(n):
    a,b = 0,1
    for i in range(n):
        a,b = a+b,a
    return a

- Jimmy

---

有一种方法可以在O(M(n)log n)的时间复杂度内计算，其中M(n)是乘法成本。对于大数，您的代码实际上是O(n^2)。请参阅我的答案，以获得快速准确的大数计算。无论如何，您都必须使用一些支持此功能的大数库或语言。 - Hynek -Pichi- Vychodil

Answer 4

您可以保存您的结果并使用它们：

public static long[] fibs;

public long fib(int n) {
    fibs = new long[n];
    return internalFib(n);
}
public long internalFib(int n) {
    if (n<=2) return 1;
    fibs[n-1] = fibs[n-1]==0 ? internalFib(n-1) : fibs[n-1];
    fibs[n-2] = fibs[n-2]==0 ? internalFib(n-2) : fibs[n-2];
    return fibs[n-1]+fibs[n-2];
}

- Ofek Ron

Answer 5

提示：您可以使用比内公式来实现更快的结果：

以下是在Python中实现的方法：

from decimal import *

def fib(n):
    return int((Decimal(1.6180339)**Decimal(n)-Decimal(-0.6180339)**Decimal(n))/Decimal(2.236067977))

- Dair

---

你所呈现的Binet公式在大数值n下不准确，因为常数1.6180339存在舍入误差。请参考我的答案（https://dev59.com/8GTWa4cB1Zd3GeqPF68U#20908253），以获得更快速和准确的计算方法。 - Hynek -Pichi- Vychodil

Answer 6

// D Programming Language 

void vFibonacci ( const ulong X, const ulong Y, const int Limit ) {    
       // Equivalent : if ( Limit != 10 ). Former ( Limit ^ 0xA ) is More Efficient However.
       if ( Limit ^ 0xA ) {    
           write ( Y, " " ) ;
           vFibonacci ( Y, Y + X, Limit + 1 ) ;
       } ;
} ;

// Call As    
// By Default the Limit is 10 Numbers
vFibonacci ( 0, 1, 0 ) ;

- Dewang

---

为了回答问题更加清晰，通常对代码进行一些简明易懂的解释是非常有益的。 - Thomas

Answer 7

F(n) = (φ^n)/√5，四舍五入到最近的整数，其中φ是黄金比例。

φ^n可以在O(lg(n))时间内计算，因此F(n)可以在O(lg(n))时间内计算。

- phoenyx

Answer 8

编辑：我认为Hynek Vychodil的答案比我的更好，但我还是保留这个答案以防有人寻找其他方法。

我认为其他方法都是有效的，但不是最优的。使用Binet公式原则上应该可以给出正确答案，但将其四舍五入到最近的整数会在n很大时产生一些问题。其他解决方案将不必要地重新计算每次调用函数时的值，因此该函数不适用于重复调用优化。

在我看来，最好的做法是定义一个全局数组，然后在需要时向数组添加新值。在Python中：

import numpy

fibo=numpy.array([1,1])
last_index=fibo.size

def fib(n):
    global fibo,last_index
    if (n>0):
        if(n>last_index):
            for i in range(last_index+1,n+1):
                fibo=numpy.concatenate((fibo,numpy.array([fibo[i-2]+fibo[i-3]])))
            last_index=fibo.size
        return fibo[n-1]
    else:
        print "fib called for index less than 1"
        quit()

如果你需要调用 n>80 的 fib 函数（大约），那么你将需要在 Python 中实现任意精度整数，这在 Python 中很容易做到。

- Tanmay Mudholkar

Answer 9

这将执行得更快，O(n)

def fibo(n):
    a, b = 0, 1
    for i in range(n):
        if i == 0:
            print(i)
        elif i == 1:
            print(i)
        else:
            temp = a
            a = b
            b += temp
    print(b)
n = int(input())
fibo(n)

- Divyanshu Kumar