Python實現(xiàn)求解斐波那契第n項的解法(包括矩陣乘法＋快速冪)
斐波那契數(shù)列
首先我們來定義一下斐波那契數(shù)列：
即數(shù)列的第0項：
算法一：遞歸
遞歸計算的節(jié)點個數(shù)是O(2ⁿ)的級別的，效率很低，存在大量的重復計算。
比如：
f(10) = f(9) + f(8)
f(9) = f(8) + f(7) 重復 8
f(8) = f(7) + f(6) 重復 7
時間復雜度是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)的復雜度是 O(1)，所以時間復雜度是 O(n)。但由于是遞歸計算，遞歸層數(shù)太多會爆棧。
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) # 不存在則計算
return res[n]
算法三：遞推
開一個大數(shù)組，記錄每個數(shù)的值。用循環(huán)遞推計算。
總共計算 n 個狀態(tài)，所以時間復雜度是 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)秀的一種解法。仔細觀察我們會發(fā)現(xiàn)，遞推時我們只需要記錄前兩項的值即可，沒有必要記錄所有值，所以我們可以用滾動變量遞推。
時間復雜度還是 O(n)，但空間復雜度變成了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
算法五：矩陣乘法+快速冪
利用矩陣運算的性質(zhì)將通項公式變成冪次形式，然后用平方倍增（快速冪）的方法求解第 n 項。
先說通式：
利用數(shù)學歸納法證明：
這里的a0,a1,a2是對應斐波那契的第幾項
證畢。
所以我們想要的得到An，只需要求得Aⁿ，然后取第一行第二個元素即可。
如果只是簡單的從0開始循環(huán)求n次方，時間復雜度仍然是O(n)，并不比前面的快。我們可以考慮乘方的如下性質(zhì)，即快速冪：
這樣只需要 logn 次運算即可得到結(jié)果，時間復雜度為 O(logn)
def mul(a, b): # 首先定義二階矩陣乘法運算
c = [[0, 0], [0, 0]] # 定義一個空的二階矩陣，存儲結(jié)果
for i in range(2): # row
for j in range(2): # col
for k in range(2): # 新二階矩陣的值計算
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]] # 單位矩陣，等價于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]
總的來說不是很難，適合擴展思路。更多關于Python的資料請關注腳本之家其它相關文章！希望大家以后多多支持腳本之家！
相關文章
Python生態(tài)圈圖像格式轉(zhuǎn)換問題(推薦)
在Python生態(tài)圈里，最常用的圖像庫是PIL——盡管已經(jīng)被后來的pillow取代，但因為pillow的API幾乎完全繼承了PIL，所以大家還是約定俗成地稱其為PIL。這篇文章主要介紹了Python生態(tài)圈圖像格式轉(zhuǎn)換問題,需要的朋友可以參考下2019-12-12
這篇文章主要介紹了Python命令啟動Web服務器實例詳解的相關資料,需要的朋友可以參考下2017-02-02
這篇文章主要介紹了pandas如何靈活增加新的空字段問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
這篇文章主要為大家詳細介紹了python用海龜繪圖寫貪吃蛇游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
這篇文章主要介紹了Python Queue模塊詳解,需要的朋友可以參考下2014-11-11
屏幕截圖是一種常見的用于記錄信息或者監(jiān)控用戶活動的方法,為了保護隱私和數(shù)據(jù)安全,可以通過使用Python編寫一些防護措施來防止他人截取我們的屏幕,下面我們就來學習一下有哪些具體操作吧2023-12-12
在本篇文章里小編給大家整理的是關于python抓取多種類型的頁面方法實例內(nèi)容，有需要的朋友們可以學習下。2019-11-11
在本篇文章里小編給各位分享了關于python怎么安裝scipy的具體方法和實例代碼，需要的朋友們學習下。2019-06-06
python list等分并從等分的子集中隨機選取一個數(shù)
這篇文章主要介紹了python list等分并從等分的子集中隨機選取一個數(shù)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-11-11
這篇文章主要介紹了Python命名空間namespace及作用域原理解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-06-06