算法导论第三版新增27章中文版(6)

计算机科学与技术

我们用 T(n) 表示 FIB(n) 的运行时间。由于 FIB(n) 包含了两个递归调用和其他一些常数时间的工作，因此得到如下递归方程：

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

我们可以采用替换方法得到该方程的解： T(n) = Θ( Fn) 。作为归纳假设，我们假设 T(n ) ≤aFn-b ，其中a>1 ，b>0 且都为常数。通过替换，我们得到：

T(n) ≤ （aF n-1 -b ）+ (aF n-2 -b ）+ Θ(1)

= a( F n-1 + F n-2 ）- 2b + Θ(1)

= aF n -b – (b- Θ(1))

≤ aF n -b

如果我们在选择b 时让其大到足以支配 Θ(1) 中的常量。那么我们接着可以把a 选得大到足以满足初始条件。其分析边界为：

T(n) = Θ( Φn ), (27.1)

其中， Φ=(1+sqrt(5))/2 是黄金分割率，由等式(3.25) 得出。由于Fn 随n 成指数级增长，因此在计算 Fibonacci 数时，该过程非常低效。（问题 31-3 中给出了快得多的方法）。