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

Question

我阅读了关于 Big O for Recursive Fibonacci sequence 的两篇文章，但仍然没有概念性地理解为什么它是 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

很多朴素的递归函数都具有指数级的复杂度，因此请牢记这一直觉。

考虑这个函数：

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

现在看到模式了吗？我们对 fiboR1 进行了 O(2^n) 次递归调用，每次调用都是一个常量时间分支。所以 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 2

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

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

Answer 3

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

由于 Fibonacci 数呈指数增长，因此将许多 1 加在一起得到它们的唯一方法是按指数方式将许多 1 相加。每个结果只会被添加到最终总数中一次，因此必须以指数方式多次执行基本情况才能将所有这些 1 生成为不同的结果。

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

What is a non-mathematical explanation for the Big O of recursive fibonacci?

javascript

big-o

fibonacci