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

algorithm time-complexity java big-o complexity-theory

2022-09-01 21:14:17

我只是尝试为各种方法实现代码（在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）。

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

答案 1

递归版本不是多项式时间 - 它是指数级的，在φⁿ处紧密限定，其中φ是黄金比率（≈1.618034）。递归版本将使用 O（n）内存（用法来自堆栈）。

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

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

（但是，实际上，早在出现性能和内存问题之前，该数字甚至可能会溢出64位整数，因此，如果要计算完整数字，则准确的分析必须考虑进行加法所需的时间）。

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

答案 2

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

}