递归斐波那契的Big O的非数学解释是什么？

Question

我阅读了有关递归斐波那契数列的大O的两篇文章，但仍然对为什么它是O（2 ^ n）尚无概念理解。

这不是此link的副本。请不要将其标记为重复项。我正在寻找概念性答案。

这是最简单的递归函数之一，我想了解如何看待它，并在没有复杂的数学和证明的情况下确定Big O。

// O(2^n)
function fiboR(n){
  if( n === 0 || n === 1 ){
    return n;
  } else if ( n >=2 ){
    return fiboR(n-1) + fiboR(n-2);
  }
}

例如，迭代版本的Big O是O（n）。我可以看到，随着n的增加，while循环迭代次数线性增加。无需复杂的数学或冗长的证明。

// O(n)
function fibo(n){
  let prev0 = 0;
  let prev1 = 1;
  if( n === 0 || n === 1 ){
    return n;
  }
  while( n-- >= 2){
    sum = prev0 + prev1;
    prev0 = prev1;
    prev1 = sum;
  }
  return sum;
}

Answer 1

通过绘制函数调用来进行计算很简单。只需为n的每个值添加函数调用，然后看数字如何增长。

大O是O（Z ^ n），其中Z是黄金分割率或大约1.62。

随着我们增加n，lenoardo数和fibonacci数都接近这个比率。

2 (2 -> 1, 0)

4 (3 -> 2, 1) (2 -> 1, 0)

8 (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)


14 (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)

            (3 -> 2, 1) (2 -> 1, 0)

22 (6 -> 5, 4)
            (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

                        (3 -> 2, 1) (2 -> 1, 0)

            (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

Answer 2

大量的朴素递归函数具有指数复杂性，因此请牢记这一直觉。

考虑此功能：

function fiboR1(n){
  if( n === 0 || n === 1 ){
    return n;
  } else if ( n >=2 ){
    return fiboR1(n-1) + fiboR1(n-1);
  }
}

好的，所以fiboR1实际上并不计算斐波那契数列。没关系请注意，其渐进复杂度至少应为fiboR。这是因为对fiboR1(n-1)的两个递归调用比对fiboR(n-1)的一个调用和对fiboR(n-2)的一个调用更昂贵。因此，让我们考虑一下fiboR1的复杂性。

让我们考虑对fiboR1(100)的示例调用。

fiboR1(100) = 2 * fiboR1(99)
            = 4 * fiboR1(98)
            = 8 * fiboR1(97)
            = 16 * fiboR1(96)
            = 32 * fiboR1(95)
            = 64 * fiboR1(94)
            ...

现在看到图案了吗？我们有对O(2^n)的fiboR1递归调用，每个调用都是一个恒定的时间分支。因此，fiboR1是O(2^n)，这意味着从广义上讲，fiboR也是O(2^n)，因为big-O是上限函数。

如果知道斐波那契数列的封闭形式，我们也可以直接对fiboR进行此示例。让我们考虑fiboR(100)：

fiboR(100) = fiboR(99) + fiboR(98)
           = 2 * fiboR(98) + fiboR(97)
           = 3 * fiboR(97) + 2 * fiboR(96)
           = 5 * fiboR(96) + 3 * fiboR(95)
           = 8 * fiboR(95) + 5 * fiboR(94)
           = 13 * fiboR(94) + 8 * fiboR(93)
           ...

递归函数调用的数量遵循斐波那契数列。斐波那契数列的闭合形式在n中是指数形式。实际上，它是O(((1+sqrt{5})/2)^n)，大约是O(1.6^n)。

Answer 3

假设您接受该函数正确，即它确实计算斐波那契数，那么很容易表明其运行时间必须是指数的：在基本情况下，它仅返回0或1，并且只能通过将较小的结果加在一起来产生较大的结果。

由于斐波那契数呈指数增长，所以将多个1加在一起就可以使它们唯一的方法是将多个1加成指数。每个结果仅被添加到最终总数一次，因此基本情况必须按指数方式执行多次，以产生所有这些1作为不同的结果。