1.簡(jiǎn)介

斐波那契數(shù)列是除了前兩個(gè)數(shù)為1，后面的每一個(gè)數(shù)都是前兩個(gè)數(shù)之和。
舉例：1,1,2,3,5,8,13.....

2.基礎(chǔ)實(shí)現(xiàn)

這邊直接用Python實(shí)現(xiàn)最基礎(chǔ)的功能，此時(shí)的時(shí)間復(fù)雜度為O（2^N），具體如何算出來的，有興趣的可以參考：斐波那契數(shù)列時(shí)間復(fù)雜度（因?yàn)檫@個(gè)問題超出了我的能力范圍。。。）

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

3.進(jìn)階實(shí)現(xiàn)

優(yōu)化之后的斐波那契數(shù)列，將之前已經(jīng)計(jì)算過得數(shù)字存儲(chǔ)起來，已備后用，這樣就不用一次次重復(fù)調(diào)用了。此時(shí)的時(shí)間復(fù)雜度為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.終極進(jìn)階

這個(gè)終極進(jìn)階是對(duì)我而言的。參考之前那篇博文啊，將時(shí)間復(fù)雜度壓縮到了O（logN）