斐波那契的算法分析

树形递归

对于斐波那契数列的定义:

$$ Fib(n)= \begin{cases} 0& \text{n=0} \\ 1& \text{n=1} \\ Fib(n-1)+Fib(n-2)& \text{Others} \end{cases} $$

我们可以很自然的将其翻译成如下递归过程:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))
  )
)

该过程为树形递归计算过程,其过程的每个调用中两次调用自身。

Fib(0) 和 Fib(1) 的计算次数

该过程中对 Fib(0) 和 Fib(1) 的计算次数(即树中的叶子节点数)为 Fib(n+1) 的值。

证明:
对于 Fib(2) 由定义可知其计算次数为2,是 Fib(3) 的值。
考虑 Fib(3) 由定义知其为 Fib(2) + Fib(1),其计算次数为3,是 Fib(4) 的值。
对于 Fib(n) 其计算过程以二叉树形式展开,显然它总会展开到 Fib(2) + Fib(1).
则数的第 n-k 层节点 Fib(k) 的左右两子节点总会返回 Fib(k) 和 Fib(k-1) 的计算次数。
合并后为 Fib(k+1).显然该过程中对 Fib(0) 和 Fib(1) 的计算次数(即树中的叶子节点数)为 Fib(n+1) 的值。

Fib(n) 的增长阶

Fib(n) 是最接近 $\frac{\phi^n}{\sqrt{5}}$ 的整数。
其中
$$\phi = \frac{1+\sqrt{5}}{2}$$
即黄金数1.618,它满足方程

$$ \phi^2=\phi+1 $$

证明:
定义 $\psi=\frac{1-\sqrt{5}}{2}$
首先证明 $Fib(n)=\frac{\phi^n-\psi^n}{\sqrt{5}}$

令 $Fib(n)=\frac{\phi^2-\psi^2}{\sqrt{5}}$

$Fib(n+1) = \frac{\phi^{n} \cdot \phi - \psi^{n} \cdot \psi}{\sqrt{5}} = \frac{\phi^{n} \cdot \frac{1+\sqrt{5}}{2} - \psi^{n} \cdot \frac{1-\sqrt{5}}{2}}{\sqrt{5}} = \frac{1}{2} \cdot Fib(n) + \frac{\phi^{n} + \psi^{n}}{2}$

$Fib(n+2) = \frac{\phi^{n} \cdot \phi^{2} - \psi^{n} \cdot \psi^{2}}{\sqrt{5}} = \frac{\phi^{n} \cdot (\frac{1+\sqrt{5}}{2})^{2} - \psi^{n} \cdot (\frac{1-\sqrt{5}}{2})^{2}}{\sqrt{5}} = \frac{3}{2} \cdot Fib(n) + \frac{\phi^{n} + \psi^{n}}{2}$

可证 Fib(n+2) = Fib(n+1) + Fib(n)
易知 Fib(0) 与 Fib(1) 时等式依旧成立。
得证 $Fib(n)=\frac{\phi^n-\psi^n}{\sqrt{5}}$

将分式拆开 $Fib(n)=\frac{\phi^n}{\sqrt{5}}-\frac{\psi^n}{\sqrt{5}}$

对数步数求斐波那契数列数

证明:

Lame 定理

如果欧几里得算法需要 k 步计算出一对整数的 GCD ,那么这对数中较小的那个数必然大于或等于 Fib(k).

证明:

Tags:SICP
上一篇
下一篇

添加新评论