斐波那契數(shù)列

首先我們來定義一下斐波那契數(shù)列：

即數(shù)列的第0項：

遞歸計算的節(jié)點(diǎn)個數(shù)是O(2ⁿ)的級別的，效率很低，存在大量的重復(fù)計算。

比如：

f(10) = f(9) + f(8)

f(9) = f(8) + f(7) 重復(fù) 8

f(8) = f(7) + f(6) 重復(fù) 7

時間復(fù)雜度是O(2ⁿ),極慢

def F1(n): if n <= 1: return max(n, 0) # 前兩項 return F1(n-1)+F1(n-2) # 遞歸算法二：記憶化搜索

開一個大數(shù)組記錄中間結(jié)果，如果一個狀態(tài)被計算過，則直接查表，否則再遞歸計算。

總共有 n 個狀態(tài)，計算每個狀態(tài)的復(fù)雜度是 O(1)，所以時間復(fù)雜度是 O(n)。但由于是遞歸計算，遞歸層數(shù)太多會爆棧。

res = [None]*100000def F2(n): if n <= 1: return max(n, 0) if res[n]: return res[n] # 如果已存在則直接查找返回結(jié)果 res[n] = F2(n-1)+F2(n-2) # 不存在則計算 return res[n]算法三：遞推

開一個大數(shù)組，記錄每個數(shù)的值。用循環(huán)遞推計算。

總共計算 n 個狀態(tài)，所以時間復(fù)雜度是 O(n)。但需要開一個長度是 n 的數(shù)組，內(nèi)存將成為瓶頸。

def F3(n): if n <= 1: return max(n, 0) res = [0, 1] for i in range(2,n+1):res.append(res[i-1]+res[i-2]) return res[n]算法四：遞歸+滾動變量

比較優(yōu)秀的一種解法。仔細(xì)觀察我們會發(fā)現(xiàn)，遞推時我們只需要記錄前兩項的值即可，沒有必要記錄所有值，所以我們可以用滾動變量遞推。

時間復(fù)雜度還是 O(n)，但空間復(fù)雜度變成了O(1)。

def F4(n): if n <= 1: return max(n, 0) fn, f0, f1 = 0, 1, 0 # fn為最終結(jié)果，f0為第0項，f1為第一項， for i in range(2, n+1):fn = f0 + f1 # 前兩項和f0, f1 = f1, fn # 遞推變量 return fn算法五：矩陣乘法+快速冪

利用矩陣運(yùn)算的性質(zhì)將通項公式變成冪次形式，然后用平方倍增（快速冪）的方法求解第 n 項。

先說通式：

利用數(shù)學(xué)歸納法證明：

這里的a0,a1,a2是對應(yīng)斐波那契的第幾項

證畢。

所以我們想要的得到An，只需要求得Aⁿ，然后取第一行第二個元素即可。

如果只是簡單的從0開始循環(huán)求n次方，時間復(fù)雜度仍然是O(n)，并不比前面的快。我們可以考慮乘方的如下性質(zhì)，即快速冪：

這樣只需要 logn 次運(yùn)算即可得到結(jié)果，時間復(fù)雜度為 O(logn)

def mul(a, b): # 首先定義二階矩陣乘法運(yùn)算 c = [[0, 0], [0, 0]] # 定義一個空的二階矩陣，存儲結(jié)果 for i in range(2): # rowfor j in range(2): # col for k in range(2): # 新二階矩陣的值計算c[i][j] += a[i][k] * b[k][j] return cdef F5(n): if n <= 1: return max(n, 0) res = [[1, 0], [0, 1]] # 單位矩陣，等價于1 A = [[1, 1], [1, 0]] # A矩陣 while n:if n & 1: res = mul(res, A) # 如果n是奇數(shù)，或者直到n=1停止條件A = mul(A, A) # 快速冪n >>= 1 # 整除2，向下取整 return res[0][1]

總的來說不是很難，適合擴(kuò)展思路。更多關(guān)于Python的資料請關(guān)注好吧啦網(wǎng)其它相關(guān)文章！希望大家以后多多支持好吧啦網(wǎng)！