algorithm - 证明这个递归斐波那契实现在 O(2^n) 时间内运行？

Question

我很难证明斐波那契的“坏”版本是 O(2^n)。IE。给定函数

int fib(int x)
{
  if ( x == 1 || x == 2 )
  {
    return 1;
  }
  else
  {
    return ( f( x - 1 ) + f( x - 2) );
  }
}

我可以得到帮助来证明这是 O(2^n)。

Answer 1

Let's start off by writing a recurrence relation for the runtime:

T(1) = 1

T(2) = 1

T(n+2) = T(n) + T(n + 1) + 1

Now, let's take a guess that

T(n) ≤ 2ⁿ

If we try to prove this by induction, the base cases check out:

T(1) = 1 ≤ 2 = 2¹

T(2) = 1 ≤ 4 = 2²

Then, in the inductive step, we see this:

T(n + 2) = T(n) + T(n + 1) + 1

≤ 2ⁿ + 2ⁿ⁺¹ + 1

< 2ⁿ⁺¹ + 2ⁿ⁺¹

= 2ⁿ⁺²

Therefore, by induction, we can conclude that T(n) ≤ 2ⁿ for any n, and therefore T(n) = O(2ⁿ).

With a more precise analysis, you can prove that T(n) = 2F_n - 1, where F_n is the nth Fibonacci number. This proves, more accurately, that T(n) = Θ(φⁿ), where φ is the Golden Ratio, which is approximately 1.61. Note that φⁿ = o(2ⁿ) (using little-o notation), so this is a much better bound.

Hope this helps!

Answer 2

Try manually doing a few test cases like f(5) and take note of how many times the method f() is called.

A fat hint would be to notice that every time the method f() is called (except for x is 1 or 2), f() is called twice. Each of those call f() two more times each, and so on...

Answer 3

使用递归树方法：

                                             T(n)                         
                                       ↙            ↘
                                   n-1              n – 2                                 
                               ↙      ↘             ↙      ↘
                           N – 2      n – 3      n – 3       n - 4   

如果您以这种方式完成递归树，则每个树级别都被视为对 fib(x - 1) fib(x - 2) 的调用，您将在 x = 1 或 x = 2（基本情况）时停止 .... 这个tree 仅显示递归树的三个级别。要解决这棵树，您需要这些重要信息： 1- 树的高度。2-每个级别完成了多少工作。这棵树的高度是 2^n，每个级别的工作量是 O(1)，那么这个递归的顺序是高度 * 每个级别的工作量 = 2^n * 1 = O(2^n)

Answer 4

实际上有一个非常简单的证明，对 的调用总数f将是2Fib(n)-1，其中Fib(n)是第 n 个斐波那契数。它是这样的：

1. f形成二叉树的一组调用，其中每个调用要么是一个叶子（对于 x=1 或 x=2），要么调用产生两个子调用（对于 x>2）。
2. 每个叶子对原始调用返回的总数贡献 1，因此存在Fib(n)总叶子。
3. 任何二叉树的内部节点总数等于L-1，其中L是叶子的数量，所以这棵树中的节点总数是2L-1。

这表明运行时间（以总调用次数衡量f）为

T(n)=2Fib(n)-1=O(Fib(n)) 

并且因为Fib(n)=Θ(φ^n),黄金比例φ在哪里

Φ=(1+sqrt{5})/2 = 1.618...

这证明了T(n) = Θ(1.618...^n) = O(n)。