斐波那契数列算法时间复杂度

斐波那契是以兔子繁殖为问题引入的数列，定义为：

F(0) = 0 ;

F(1) = 1 ;

F(n) =  F(n-1)+F(n-2) ;  n>=2

得到这样一组数列：0,1,1,2,3,5,8,13,21,34,55,89…..

关于斐波那契数列定义应用等详见百度百科

求解斐波那契数列通常有两种方法：1、递归算法 2、非递归算法

1、递归算法

递归算法很简单，根据定义很容易写出

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

求递归算法时间复杂度

设：f(n)为参数n的时间复杂度，根据 f(n) = f(n-1) + f(n-2)

转化成求解数学问题，求解二阶常系数差分方程。

特征方程 x^2-x-1=0

求解特征方程得到：x=(1±√5)/2

得出f(n)的通解为：

因为f(0)=0,f(1)=1，计算得到C1,C2

所以F(n)通项为：

（具体计算推导方法可以参考百度百科）

所以时间复杂度 T(n) = O[(1/2)^n] = O(2^n)

因为递归算法中会重复调用，所以时间复杂度较高

2、非递归算法

另一种方法是使用非递归算法。

首先赋值为f(0)=0,f(1)=1

然后后边的每一项都是前两项的和，算法如下

def fib2(n):
    s1, s2 = 0, 1
    if n == 0:
        return s1
    elif n == 1:
        return s2
    else:
        for i in range(1, n):
            s1, s2 = s2, s1+s2
        return s2

可以很明显的看到计算第n项的时间复杂度为 T(n) = O(n)

3、还有一种非递归算法是使用矩阵

根据斐波那契数列定义，我们有：

所以计算f(n)的值变成了计算二阶矩阵的(n-1)次方值，根据以上分析可以写出矩阵次方计算代码

python矩阵操作需要导入一个numpy包

from numpy import *
def fib3(n):
    a = mat(([[1, 1], [1, 0]]))
    b = mat([[1], [0]])
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        c = pow(a, n-1) * b
        return c[0, 0]

总结：

根据以上三种不同方法计算得到的斐波那契数列如下：