av一区二区在线观看_亚洲男人的天堂网站_日韩亚洲视频_在线成人免费_欧美日韩精品免费观看视频_久草视

您的位置:首頁(yè)技術(shù)文章
文章詳情頁(yè)

Python實(shí)現(xiàn)求解斐波那契第n項(xiàng)的解法(包括矩陣乘法+快速冪)

瀏覽:75日期:2022-06-22 13:51:25

斐波那契數(shù)列

首先我們來(lái)定義一下斐波那契數(shù)列:

Python實(shí)現(xiàn)求解斐波那契第n項(xiàng)的解法(包括矩陣乘法+快速冪)

即數(shù)列的第0項(xiàng):

Python實(shí)現(xiàn)求解斐波那契第n項(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]*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) # 不存在則計(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ō)通式:

Python實(shí)現(xiàn)求解斐波那契第n項(xiàng)的解法(包括矩陣乘法+快速冪)

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

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

Python實(shí)現(xiàn)求解斐波那契第n項(xiàng)的解法(包括矩陣乘法+快速冪)

證畢。

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

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

Python實(shí)現(xiàn)求解斐波那契第n項(xiàng)的解法(包括矩陣乘法+快速冪)

這樣只需要 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): # rowfor j in range(2): # col for k in range(2): # 新二階矩陣的值計(jì)算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]] # 單位矩陣,等價(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ō)不是很難,適合擴(kuò)展思路。更多關(guān)于Python的資料請(qǐng)關(guān)注好吧啦網(wǎng)其它相關(guān)文章!希望大家以后多多支持好吧啦網(wǎng)!

標(biāo)簽: Python 編程
相關(guān)文章:
主站蜘蛛池模板: 亚洲网视频 | 99re国产 | 高清国产午夜精品久久久久久 | 91精品国产91久久久久游泳池 | 国产91在线播放精品91 | 免费一区在线观看 | 国产欧美日韩在线观看 | 亚洲精品v日韩精品 | 国产精品自产拍在线观看蜜 | 99久久婷婷国产精品综合 | av免费网址| 欧美午夜一区 | 中文字幕不卡视频在线观看 | 国产午夜精品一区二区三区四区 | 欧美视频免费在线 | 国产黄色小视频在线观看 | 亚洲成年在线 | 亚洲精品影院 | 亚洲精品久久久久国产 | 精品视频一区二区三区在线观看 | 色www精品视频在线观看 | 日韩一级黄色片 | 韩日一区二区三区 | 亚洲福利在线视频 | 日韩久久久久久久久久久 | 亚洲精品电影网在线观看 | 亚洲精品在线播放 | 色视频在线播放 | 午夜a√ | 91久操视频 | 日韩成人在线视频 | 中文字幕在线一区二区三区 | 亚洲一区二区三区四区五区午夜 | 国产色爽 | 秋霞a级毛片在线看 | 日韩快播电影网 | 精品久久久久久久久久 | 成人精品一区二区 | 亚洲区在线 | 成人夜晚看av | 午夜国产一级 |