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

Question

我阅读了关于递归斐波那契数列的 Big O 的两篇文章，但仍然没有概念性地理解为什么它是O(2^n)。

这不是此链接的副本。请不要标记为重复。我正在寻找一个概念性的答案。

这是最简单的递归函数之一，我想了解如何看待它并在没有复杂数学和证明的情况下确定大 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 时，莱诺阿多数和斐波那契数都接近这个比率。

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)