斐波那契數(shù)列作為一個(gè)非常經(jīng)典的數(shù)學(xué)問(wèn)題，在我們學(xué)習(xí)編程語(yǔ)言遞歸思想的時(shí)候，這個(gè)問(wèn)題經(jīng)常被拿來(lái)應(yīng)用。下面我將為大家介紹使用Python求解斐波那契數(shù)列第n項(xiàng)的多種算法。
斐波那契數(shù)列
首先我們來(lái)定義一下斐波那契數(shù)列：
即數(shù)列的第0項(xiàng)：
算法一：遞歸
遞歸計(jì)算的節(jié)點(diǎn)個(gè)數(shù)是O(2?)的級(jí)別的，效率很低，存在大量的重復(fù)計(jì)算。
比如：
f(10) = f(9) + f(8)
f(9) = f(8) + f(7) 重復(fù) 8
f(8) = f(7) + f(6) 重復(fù) 7
時(shí)間復(fù)雜度是O(2?),極慢
def F1(n):
if n <= 1: return max(n, 0) # 前兩項(xiàng)
return F1(n-1)+F1(n-2) # 遞歸算法二：記憶化搜索
開(kāi)一個(gè)大數(shù)組記錄中間結(jié)果，如果一個(gè)狀態(tài)被計(jì)算過(guò)，則直接查表，否則再遞歸計(jì)算。
總共有 n 個(gè)狀態(tài)，計(jì)算每個(gè)狀態(tài)的復(fù)雜度是 O(1)，所以時(shí)間復(fù)雜度是 O(n)。但由于是遞歸計(jì)算，遞歸層數(shù)太多會(huì)爆棧。
res = [None]*100000
def F2(n):
if n <= 1: return max(n, 0)
if res[n]: return res[n] # 如果已存在則直接查找返回結(jié)果
res[n] = F2(n-1)+F2(n-2) # 不存在則計(jì)算
return res[n]
算法三：遞推
開(kāi)一個(gè)大數(shù)組，記錄每個(gè)數(shù)的值。用循環(huán)遞推計(jì)算。
總共計(jì)算 n 個(gè)狀態(tài)，所以時(shí)間復(fù)雜度是 O(n)。但需要開(kāi)一個(gè)長(zhǎng)度是 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]
算法四：遞歸+滾動(dòng)變量
比較優(yōu)秀的一種解法。仔細(xì)觀察我們會(huì)發(fā)現(xiàn)，遞推時(shí)我們只需要記錄前兩項(xiàng)的值即可，沒(méi)有必要記錄所有值，所以我們可以用滾動(dòng)變量遞推。
時(shí)間復(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項(xiàng)，f1為第一項(xiàng)，
for i in range(2, n+1):
fn = f0 + f1 # 前兩項(xiàng)和
f0, f1 = f1, fn # 遞推變量
return fn
算法五：矩陣乘法+快速冪
利用矩陣運(yùn)算的性質(zhì)將通項(xiàng)公式變成冪次形式，然后用平方倍增（快速冪）的方法求解第 n 項(xiàng)。
先說(shuō)通式：
利用數(shù)學(xué)歸納法證明：
這里的a0,a1,a2是對(duì)應(yīng)斐波那契的第幾項(xiàng)
證畢。
所以我們想要的得到An，只需要求得A?，然后取第一行第二個(gè)元素即可。
如果只是簡(jiǎn)單的從0開(kāi)始循環(huán)求n次方，時(shí)間復(fù)雜度仍然是O(n)，并不比前面的快。我們可以考慮乘方的如下性質(zhì)，即快速冪：
這樣只需要 logn 次運(yùn)算即可得到結(jié)果，時(shí)間復(fù)雜度為 O(logn)
def mul(a, b): # 首先定義二階矩陣乘法運(yùn)算
c = [[0, 0], [0, 0]] # 定義一個(gè)空的二階矩陣，存儲(chǔ)結(jié)果
for i in range(2): # row
for j in range(2): # col
for k in range(2): # 新二階矩陣的值計(jì)算
c[i][j] += a[i][k] * b[k][j]
return c
def F5(n):
if n <= 1: return max(n, 0)
res = [[1, 0], [0, 1]] # 單位矩陣，等價(jià)于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]總的來(lái)說(shuō)，按照文章看下來(lái)操作一遍會(huì)發(fā)現(xiàn)解斐波那契數(shù)列問(wèn)題其實(shí)也不是很難，難得是自己獨(dú)立寫的時(shí)候是否有那種編程思維。本篇文章供大家學(xué)習(xí)參考，想要了解更多關(guān)于 Python 其他資料請(qǐng)關(guān)注W3Cschool其它相關(guān)文章！希望大家以后多多支持我們！
