java 各种斐波那契实现的 Big-O

Big-O for various Fibonacci Implementations

提问by

I just tried implementing code (in Java) for various means by which the nth term of the Fibonacci sequence can be computed and I'm hoping to verify what I've learnt.

我只是尝试以各种方式实现代码（在 Java 中），通过这些方式可以计算斐波那契数列的第 n 项，我希望验证我所学到的。

The iterative implementation is as follows:

迭代实现如下：

public int iterativeFibonacci(int n)
{
  if ( n == 1 ) return 0;
  else if ( n == 2 ) return 1;
  int i = 0, j = 1, sum = 0;
  for ( ; (n-2) != 0; --n )
  {
    sum = i + j;
    i = j;
    j = sum;
  }
  return sum;
}

The recursive implementation is as follows :-

递归实现如下：-

  public int recursiveFibonacci(int n)
  {
    if ( n == 1 ) return 0;
    else if ( n == 2 ) return 1;
    return recursiveFibonacci(n-1) + recursiveFibonacci(n-2);
  }

The memoized implementation is as follows :-

记忆的实现如下：-

  public int memoizedFibonacci(int n)
  {
    if ( n <= 0 ) return -1;
    else if ( n == 1 ) return 0;
    else if ( n == 2 ) return 1;
    if ( memory[n-1] == 0 )
      memory[n-1] = memoizedFibonacci(n-1);
    if ( memory[n-2] == 0 )
      memory[n-2] = memoizedFibonacci(n-2);
    return memory[n-1]+memory[n-2];
  }

I'm having a bit of a doubt when trying to figure out the Big-O of these implementations. I believe the iterative implementation to be O(n)as it loops through N-2 times.

在试图找出这些实现的大 O 时，我有点怀疑。我相信迭代实现是 O(n)，因为它循环 N-2 次。

In the recursive function, there are values recomputed, hence I think it's O(n^2).

在递归函数中，有重新计算的值，因此我认为它是O(n^2)。

In the memoized function, more than half of the values are accessed based on memoization. I've read that an algorithm is O(log N) if it takes constant time to reduce the problem space by a fractionand that an algorithm is O(N) if it takes constant time to reduce the problem space by a constant amount. Am I right in believing that the memoized implementation is O(n)in complexity? If so, wouldn't the iterative implementation be the best among all three? (as it does not use the additional memory that memoization requires).

在 memoized 函数中，超过一半的值是基于 memoization 访问的。我读过的算法是为O（log N），如果它需要一定的时间通过一小部分，以减少问题空间以及一个算法是O（N），如果它需要一定的时间以恒定量减少的问题空间。我认为记忆化实现的复杂性是O(n)是否正确？如果是这样，迭代实现不是三者中最好的吗？（因为它不使用记忆所需的额外内存）。

采纳答案by nhahtdh

The recursive version is not polynomial time - it's exponential, tightly bounded at φⁿwhere φ is the golden ratio (≈ 1.618034). The recursive version will use O(n) memory (the usage comes from the stack).

递归版本不是多项式时间 - 它是指数型的，严格限制在 φ ⁿ处，其中 φ 是黄金比例（≈ 1.618034）。递归版本将使用O( n) 内存（使用量来自堆栈）。

The memoization version will take O(n) time on first run, since each number is only computed once. However, in exchange, it also take O(n) memory for your current implementation (the ncomes from storing the computed value, and also for the stack on the first run). If you run it many times, the time complexity will become O(M+ q) where Mis the max of all input nand qis the number of queries. The memory complexity will become O(M), which comes from the array which holds all the computed values.

memoization 版本在第一次运行时将花费O( n) 时间，因为每个数字只计算一次。但是，作为交换，您当前的实现也需要O( n) 内存（n来自存储计算值，以及第一次运行时的堆栈）。如果你运行了很多次，时间复杂度将成为Ø（中号+ q），其中中号是所有输入的最大ñ和q是查询的数量。内存复杂度将变为O( M)，它来自保存所有计算值的数组。

The iterative implementation is the best if you consider one run, as it also runs in O(n), but uses constant amount of memory O(1) to compute. For a large number of runs, it will recompute everything, so its performance may not be as good as memoization version.

如果您考虑一次运行，迭代实现是最好的，因为它也在O( n) 中运行，但使用恒定数量的内存O(1) 进行计算。对于大量运行，它会重新计算所有内容，因此其性能可能不如 memoization 版本。

(However, practically speaking, long before the problem of performance and memory, the number is likely to overflow even 64-bit integer, so an accurate analysis must take into account the time it takes to do addition if you are computing the full number).

（不过，实际来说，早在性能和内存问题之前，即使是64位整数也有可能溢出，所以准确的分析必须考虑到计算全数时进行加法所需的时间） .

As plesiv mentioned, the Fibonacci number can also be computed in O(log n) by matrix multiplication (using the same trick as fast exponentiation by halving the exponent at every step).

正如 plesiv 所提到的，Fibonacci 数也可以通过矩阵乘法以O(log n)计算（使用与快速求幂相同的技巧，通过在每一步将指数减半）。

回答by Paul92

A java implementation to find Fibonacci number using matrix multiplication is as follows:

使用矩阵乘法查找斐波那契数的 java 实现如下：

private static int fibonacci(int n)
{
    if(n <= 1)
        return n;

    int[][] f = new int[][]{{1,1},{1,0}};

    //for(int i = 2; i<=n;i++)
        power(f,n-1);

    return f[0][0];
}

// method to calculate power of the initial matrix (M = [][]{{1,1},{1,0}})

private static void power(int[][] f, int n)
{
    int[][] m = new int[][]{{1,1},{1,0}};

    for(int i = 2; i<= n; i++)
        multiply(f, m);


}

// method to multiply two matrices
private 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;



}

Even another faster method than Matrix exponentiation method to calculate Fibonacci number is Fast Doubling method. The amortized time complexity for both the methods is O(logn). The method follows the following formula F(2n) = F(n)[2*F(n+1) – F(n)] F(2n + 1) = F(n)2 + F(n+1)2

比矩阵求幂法计算斐波那契数的另一种更快的方法是快速加倍法。这两种方法的摊销时间复杂度都是 O(logn)。该方法遵循以下公式 F(2n) = F(n)[2*F(n+1) – F(n)] F(2n + 1) = F(n)2 + F(n+1)2

One such java implementation for Fast Doubling method is as below:

快速加倍方法的一个这样的java实现如下：

private static void fastDoubling(int n, int[] ans)
{
    int a, b,c,d;

    // base case
    if(n == 0)
    {
        ans[0] = 0;
        ans[1] = 1;
        return;
    }

    fastDoubling((n/2), ans);

    a = ans[0];  /* F(n) */
    b = ans[1];  /* F(n+1) */
    c = 2*b-a;

    if(c < 0)
        c += MOD;

    c = (a*c) % MOD;  /* F(2n)  */
    d = (a*a + b*b) % MOD ;  /*  F(2n+1) */

    if(n%2 == 0)
    {
        ans[0] = c;
        ans[1] = d;
    }
    else
    {
        ans[0] = d;
        ans[1] = (c+d);
    }

}