算法之斐波那契数

• 算法之斐波那契数
• 定义
• 递归解法
• 循环写法，cache结果
• 利用数学结果1
• 利用数学结果2
• 实验
• 结论

定义

斐波那契数递归地定义为：
[ F_0 = 0\;F_1 =1\;F_i = F_{i-1} + F_{i-2}\;当i \geq 2]

递归解法

这是根据定义直接求解。以指数形式增长。

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

循环写法，cache结果

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        n2 = 0
        n1 = 1
        r = 1
        while n > 2:
            n2 = n1
            n1 = r
            r = n2 + n1
            n -= 1
    return r

利用数学结果1

事实上，有这么一个数学结论：

[F_i = \frac{\phi^i-\hat\phi^i}{\sqrt{5}}, 其中\phi=\frac{1+\sqrt{5}}{2}, \hat\phi=\frac{1-\sqrt{5}}{2}]

似乎能够利用分治法举例之x的n次方获得解。但仔细想想，这公式里有(\sqrt{5}), 肯定会在计算中丢失精度，而斐波那契数一定是个整数。这玩意并不能真正用程序来实现。

利用数学结果2

还有这么一个数学公式：(可以用归纳法证明)

[ \begin{pmatrix}
F_{n+1} & F_n \
F_n & F_{n-1}
\end{pmatrix} =
\begin{pmatrix}
1 & 1 \
1 & 0
\end{pmatrix}^n
]

而计算一个数的n次方，可以利用分治法举例之x的n次方了，可以知道时间复杂度是(\Theta(logn))

一用了numpy的矩阵相乘，但是在计算到93时出了错误，应该是数字越界问题。重新实现了下。

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1

    class metrix:
        def __init__(self, i1, i2, j1, j2):
            self.i1 = i1
            self.i2 = i2
            self.j1 = j1
            self.j2 = j2

        def mul(self, another):
            i1 = self.i1 * another.i1 + self.i2 * another.j1
            i2 = self.i1 * another.i2 + self.i2 * another.j2
            j1 = self.j1 * another.i1 + self.j2 * another.j1
            j2 = self.j1 * another.i2 + self.j2 * another.j2
            return metrix(i1, i2, j1, j2)

        def __str__(self):
            return "(i1=%ld,i2=%ld,j1=%ld,j2=%ld)" % (
                self.i1, self.i2, self.j1, self.j2)

        @staticmethod
        def mulmetirx(a, b):
            return a.mul(b)

    def metrix_power(x, n):
        if n == 0:
            return 1
        elif n == 1:
            return x
        else:
            return metrix.mulmetirx(metrix_power(x, int(n/2)),
                                    metrix_power(x, n-int(n/2)))
    base = metrix(1, 1, 1, 0)
    result = metrix_power(base, n)
    return result.i2

实验

结论

最简单的写法简直惨不忍睹，而高效的算法太依赖于数学了。算法和数学真的不分家，有志于玩算法的同学，学好数学吧。
更多的时候，我们要选择的不是最优的，而是最合适的。
譬如在1万以下，O(n)的效率居然最高。直到到了10万，O(lgn)才比O(n)更好。