1.简介

斐波那契数列是除了前两个数为1，后面的每一个数都是前两个数之和。
举例：1,1,2,3,5,8,13.....

2.基础实现

这边直接用Python实现最基础的功能，此时的时间复杂度为O（2^N），具体如何算出来的，有兴趣的可以参考：斐波那契数列时间复杂度（因为这个问题超出了我的能力范围。。。）

def fibonacci_origin(n):
    if n < 3:
        return 1
    else:
        return fibnoacci_origin(n-1) + fibnoacci_origin(n-2)

3.进阶实现

优化之后的斐波那契数列，将之前已经计算过得数字存储起来，已备后用，这样就不用一次次重复调用了。此时的时间复杂度为O（N）

def fibonacci_improve(n):
    sum1 = 1
    first = 1
    second = 1
    count = 3
    while count <= n:
        n -= 1
        sum1 = first + second
        first = second 
        second = sum1
    #print(time.time()-start)
    return sum1 

4.终极进阶

这个终极进阶是对我而言的。参考之前那篇博文啊，将时间复杂度压缩到了O（logN）