iT邦幫忙

2021 iThome 鐵人賽

0
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 34

【Day34】[演算法]-費波那契數列Fibonacci Sequence

之前在遞迴的篇章有介紹過費波那契數列,是使用遞迴的方式實作,但是從下面遞迴的樹狀圖來看,會發現有很多重複的節點,遞迴的深度越深,重複計算的節點也就越多,甚至會出現RecursionError的情況,而這樣的時間複雜度為O(2^n)。
https://ithelp.ithome.com.tw/upload/images/20211015/20121027PQhJA2oGXY.jpg
https://ithelp.ithome.com.tw/upload/images/20211015/20121027w33ThcZSUU.png


因此可以將會重複計算的部分暫存起來避免重覆計算來增加處理效能。

def fibonacci(n):
    if n == 0 or n == 1:
        return n
    seq = [0 for _ in range(n + 1)]
    seq[0] = 0
    seq[1] = 1
    for i in range(2, n + 1):
      seq[i] = seq[i-1] + seq[i-2]
    return seq[n]

fibonacci(8)#21
  • 建立一個seq列表
  • seq[i]為F(i)的值,可以說seq[i] = seq[i-1] + seq[i-2]
  • 把seq[0]為0、seq[1]為1
  • 用迴圈計算i=2到n+1時,得出seq[i]的結果,儲存於seq列表中被使用
  • 最後算出來的seq[n],就是F(n)的值

透過上面的方式,可以發現真正被計算到的只剩下橘色部分藍色框為已經被儲存在seq列表中,不需要重複計算,時間複雜度變為O(n)
https://ithelp.ithome.com.tw/upload/images/20211015/201210270aqGI7Z1HW.jpg


根據上述方式,空間複雜度為O(n),但還可以有更進階的方式來節省空間

def fibonacci(n):
    if n == 0 or n == 1:
        return n
    a = 0
    b = 1
    for i in range(2, n+1):
        c = a + b
        a = b
        b = c
    return b

fibonacci(8)#21
  • 開始的前兩項a與b,為0與1
  • 後一項c是前兩項的加總
  • 只需要對a和b不斷重新賦值

空間複雜度就能從原本的O(n)變成O(1)。


上一篇
【Day33】[演算法]-深度優先搜尋DFS與廣度優先搜尋BFS
下一篇
【Day35】[演算法]-常見的演算法策略Algorithmic Patterns
系列文
資料結構與演算法,使用JavaScript與Python35

尚未有邦友留言

立即登入留言