各种斐波那契实施的大O.

Question

我只是尝试用各种方法实现代码(在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)？如果是这样,那么迭代实现不是所有三者中最好的吗？(因为它不使用memoization所需的额外内存).

Answer 1

递归版本不是多项式时间-这是指数,在φ紧紧包围^ñ其中φ是黄金比例(≈1.618034).递归版本将使用O(n)内存(使用来自堆栈).

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

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

(但是,实际上,早在性能和内存问题出现之前,数字很可能会溢出甚至64位整数,因此如果计算完整数,则准确分析必须考虑添加所需的时间) .

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