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

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

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]

总结:

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

 

您可能还喜欢...