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

Question

我很难证明斐波那契的"坏"版本是O（2^n）。即。给定函数

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

我可以得到帮助来证明这是 O（2^n） 吗？

Answer 1

让我们从为运行时编写递归关系开始：

T（1） = 1

T（2） = 1

T（n+2） =

T（n） + T（n + 1） + 1

现在，让我们猜一猜

T（n） ≤ 2ⁿ

如果我们尝试通过归纳来证明这一点，则基本情况会检查：

T（1） = 1 ≤ 2 = 2¹

T（2） = 1 ≤ 4 = 2²

然后，在归纳步骤中，我们看到：

T（n + 2） = T（n） +

T（n + 1） + 1

≤ 2ⁿ + 2ⁿ⁺¹ + 1

<2>ⁿ⁺¹ + 2ⁿ⁺¹

= 2ⁿ⁺²

因此，通过归纳，我们可以得出结论，对于任何n，T（n）≤2ⁿ，因此T（n）= O（2ⁿ）。

通过更精确的分析，您可以证明 T（n） = 2F n - 1，其中 F n 是第_n 个斐波那契数。 这更准确地证明了 T（n） = Θ（φⁿ），其中 φ 是黄金比例，大约为 1.61。 请注意，φ n = o（2ⁿ）（使用 little-o 表示法），因此这是一个更好的界限。

希望这有帮助！

Answer 2

尝试手动执行一些测试用例，例如f(5)，并记下调用方法f()的次数。

一个重要的提示是，每次调用方法 f() 时（x 是 1 或 2 除外），f() 都会被调用两次。他们每个人的电话f()两次，依此类推......

Answer 3

实际上

有一个非常简单的证明，对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).

Answer 4

使用递归树方法：

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

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