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

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)。有人可以给我一个更省时的递归算法吗？

score 3 · Accepted Answer

在此处查找使用公式的 Erlang 中的实现 $\begin{pmatrix}1&1\\1&0\end{pmatrix}^{n-1}=\begin{pmatrix}\mathrm{fib}(n)&\mathrm{fib}(n-1)\ \mathrm{fib }(n-1)&\mathrm{fib}(n-2)\end{pmatrix}$ 。它显示了很好的线性结果行为，因为O(M(n) log n)部分M(n)是大数字的指数。它在 2 秒内计算出一百万的 fib，其中结果有 208988 位。诀窍是您可以O(log n)使用（尾）递归公式计算乘法中的幂（尾表示O(1)在使用适当的编译器或重写循环时带有空格）：

% 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将以 $\begin{pmatrix}1&1\1&0\end{pmatrix}$ 和Acc身份启动I等于 $\begin{pmatrix}1&0\0&1\end{pmatrix}$ 。

score 2 · Accepted Answer

一种简单的方法是迭代地而不是递归地计算它。这将在线性时间内计算 F(n)。

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

score 2 · Accepted Answer

我已经阅读了一些以有效时间复杂度计算斐波那契的方法，以下是其中一些 -

方法 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 次（换句话说，计算幂（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) 时间复杂度下工作。我们可以在前面的方法中进行递归乘法得到幂（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) 这个公式如何工作？该公式可以从上述矩阵方程推导出来。斐波那契矩阵

两边取行列式，我们得到 (-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]; 
}

方法 4 - 使用公式 在此方法中，我们直接实现斐波那契数列中第 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

score 1 · Accepted Answer

提示：获得更快结果的一种方法是使用Binet 公式：

这是在 Python 中执行此操作的一种方法：

from decimal import *

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

score 1 · Accepted Answer

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

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];
}

score 0 · Accepted Answer

编辑：我实际上认为 Hynek Vychodil 的答案比我的要好，但我把它留在这里以防万一有人正在寻找替代方法。

我认为其他方法都是有效的，但不是最优的。使用 Binet 的公式原则上应该会给您正确的答案，但是四舍五入到最接近的整数会在 n 的较大值时产生一些问题。每次调用该函数时，其他解决方案将不必要地重新计算最多 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 中很容易做到。

score 0 · Accepted Answer

// 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 ) ;

score 0 · Accepted Answer

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

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

score -1 · Accepted Answer

这将执行得更快，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)

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

9 回答 9

Related

Reference