各种斐波那契实现的Big-O [英] Big-O for various Fibonacci Implementations

问题描述

我只是尝试以各种方式实现代码(Java)，从而可以计算出斐波那契数列的第n个项，我希望验证自己学到了什么.

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.

迭代实现如下:

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次.

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(n ^ 2).

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

在记忆功能中，超过一半的值是基于记忆访问的.我已经读到，如果将问题空间减少一小部分所需的时间不变，那么算法是O(log N)，如果花费恒定的时间，算法是O(N)减少问题空间的固定数量.我是否相信所记住的实现复杂度 O(n)是对的吗?如果是这样，那么迭代实现不是这三个方法中最好的吗?(因为它不使用备注所需的额外内存).

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 fraction and 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).

推荐答案

递归版本不是多项式时间-它是指数形式，紧密绑定在φ ⁿ 其中φ是黄金分割率(≈1.618034).递归版本将使用 O ( n )内存(用法来自堆栈).

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).

由于每个数字仅计算一次，因此该备忘录版本将在第一次运行时花费 O ( n )时间.但是，作为交换，您当前的实现也需要占用 O ( n )内存( n 来自存储计算的值，并且对于第一次运行的堆栈).如果多次运行，时间复杂度将变为 O ( M + q )，其中 M 是所有输入 n 和 q 的最大值是查询数.内存复杂度将变为 O ( M )，它来自保存所有计算值的数组.

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 n comes 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 M is the max of all input n and q is the number of queries. The memory complexity will become O(M), which comes from the array which holds all the computed values.

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

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.

(但是，实际上，早在性能和内存问题出现之前，该数字很可能甚至会溢出64位整数，因此，如果要计算全数字).

(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).

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

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).

这篇关于各种斐波那契实现的Big-O的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！