23

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

迭代实现如下：

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

递归实现如下：-

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

记忆的实现如下： -

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

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

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

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

4

2 回答 2

22

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

记忆版本在第一次运行时将花费O ( n ) 时间，因为每个数字只计算一次。但是，作为交换，您当前的实现也需要O ( n ) 内存（ n来自存储计算值，也用于第一次运行时的堆栈）。如果多次运行，时间复杂度将变为O ( M + q )，其中M是所有输入n的最大值，q是查询数。内存复杂度将变为O ( M )，它来自包含所有计算值的数组。

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

（但实际上，早在性能和内存问题之前，即使是 64 位整数，数字也可能溢出，因此准确分析必须考虑计算完整数字时进行加法所需的时间） .

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

于 2012-11-18T12:34:21.237 回答
0

使用矩阵乘法查找斐波那契数的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;



}

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

一种用于快速加倍方法的 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);
    }

}
于 2018-04-08T20:23:53.993 回答