Fibonacci(斐波那契)序列的4种求解算法

Fibonacci(斐波那契)序列, 其求解算法, 很多编程书都会以其作为例子.

1. 最普遍的算法是利用递归:

def fibonacci(n):
    return n>=2 and fibonacci(n-2)+fibonacci(n-1) or n
看上去非常美妙,但其时间复杂度是非常惊人的: O(2^n) :(
2. 另一个常见的算法, 就是用循环取代递归算法:
def fibonacci(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a+b
    return a
其时间复杂度为: O(n), 相比第1种递归算法, 已经是一种”飞跃”了 :> 它也有其变种, 就是利用 Python 的 generator, 其原理是一样, 只是应用的场合不一样罢了
def fibonacci():
    a, b = 0, 1
    while 1:
        yield a
        a, b = b, a+b

f = fibonacci()
n = 100
for i in range(n+1):
    print(next(f))
3. 最后一种算法是利用矩阵运算来加速:
import numpy

fibonacci_matrix = numpy.matrix([[1,1],[1,0]], dtype=numpy.ndarray)
def fibonacci(n):
    return fibonacci_matrix**(n-1)[0, 0]
需要用到 numpy 库, 其时间复杂度为: O(logn).
4. 通过 Fibonacci 序列的通用公式, 可以利用简单的数学方法求其近似值: 
from math import sqrt
 
def fibonacci(n):
    return int(((1+sqrt(5))/2)**n/sqrt(5))
虽然这是4种算法中速度最快的, 但当n越大,其计算精度偏差越大 :>