斐波那契数列算法时间复杂度
斐波那契是以兔子繁殖为问题引入的数列,定义为:
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]
总结:
根据以上三种不同方法计算得到的斐波那契数列如下: