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

让我们从编写运行时的递归关系开始:

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。请注意 φⁿ = o(2ⁿ)(使用小 o 表示法)，因此这是一个更好的界限。

希望这对您有所帮助!