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

Question

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

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

这是最简单的递归函数之一，我想了解如何在没有复杂数学和证明的情况下查看它并确定大 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);
  }
}

例如迭代版本的大 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 数和斐波那契数都接近这个比率。

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)