证明这个递归的Fibonacci实现在时间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 ^{N + 1} + 1

<2 ^{n + 1} + 2 ^{n + 1}

= 2 ^{n + 2}

因此,通过感应,我们可以得出结论,T(N)≤2 ^Ñ对任意n,因此T(N)= O(2 ^Ñ).

通过更精确的分析,您可以证明T(n)= 2F _n - 1,其中F _n是第n个Fibonacci数.这证明,更准确地,即T(N)=Θ(φ ^Ñ),其中φ是黄金比例,这大约是1.61.注意,φ ^Ñ = O(2 ^Ñ)(使用小O符号),所以这是一个更好的结合.

希望这可以帮助!