算法之斐波那契数

算法之斐波那契数

定义

斐波那契数递归地定义为:
[ 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

实验

实现 规模 结果 时间 时间复杂度
递归实现 10 55 0.036 指数级
循环+cache 10 55 0.035 O(n)
矩阵算法 10 55 0.251 O(lgn)
递归实现 100 >83秒后终止 指数级
循环+cache 100 354224848179261915075 0.037 O(n)
矩阵算法 100 354224848179261915075 0.061 O(lgn)
循环+cache 1000 0.036 O(n)
矩阵算法 1000 0.061 O(lgn)
循环+cache 10000 0.069 O(n)
矩阵算法 10000 0.111 O(lgn)
循环+cache 100000 0.279 O(n)
矩阵算法 100000 0.627 O(lgn)
循环+cache 1000000 18.941 O(n)
矩阵算法 1000000 6.586 O(lgn)

结论

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注