#42824: python 如果你想用遞迴，但不想吃TLE
sam851015@gmail.com
(多挖鼻孔有益身心健康)
學校
:
不指定學校
編號 : 277705
來源 : [123.192.228.253]
最後登入時間 ：
2024-11-09 20:16:56
k402. 費氏數列
| From: [123.192.228.253] |
發表日期
:
2024-10-06 03:31
我猜你的直覺反應可能是寫一個像這樣的函數(我也這樣)
|
def fib(n: int) -> int:
if n == 1:
return 0
if n == 2:
return 1
return fib(n - 1) + fib(n - 2)
|
然後就吃 TLE 了
也許你會開始懷疑人生，難道遞迴的效率真的那麼糟糕????
遞迴確實會稍微影響效率，但沒有影響那麼誇張，主要問題出在這個寫法有很多重複而冗於的計算
如果我們今天要計算 fib(6) 的值，函數會這樣展開:
| fib(6) = fib(5) + fib(4) fib(5) = fib(4) + fib(3) fib(4) = fib(3) + fib(2) fib(3) = fib(2) + fib(1) |
仔細觀察可以注意到有一些過程被重複計算了，例如:
fib(6) 中，為了求出 fib(5) ，需要計算 fib(1) 到 fib(4) 的值
為了求出 fib(4) ，需要計算 fib(1) 到 fib(3) 的值
fib(3) 被重複計算了 2 次!!
現在想像一下如果要求 fib(10) 甚至更大的數字時，fib(3) 會被重複計算多少次
而且還不只fib(3)會被重複計算，還有 fib(4)、fib(5)、fib(6) 等著被重複計算
時間複雜度是 O(n^2)
這就是效率差的原因
為了不重覆計算已經做過的結果，需要把已經做過的答案記錄起來，這個動作叫 記憶化Memoization
|
def fib(n: int, temp=None) -> int:
if temp == None:
temp = {1: 0, 2: 1}
if n in temp:
return temp[n]
temp[n] = fib(n - 1, temp) + fib(n - 2, temp)
return temp[n]
|
這邊我用 dict 保存第 n 項的內容(你要用 list 也可以)，建立一個參數 temp 用來紀錄結果，預設為 None
(寫 Python 盡量不使用可變參數做為參數預設值是好習慣，曾搞垮一家大公司，想理解原因看這篇)
初次調用函數時，如果發現 temp 是 None，就建立一份新的
之後每次遞迴都只需要檢查答案有沒有被記錄過，如果沒有就記錄起來，如果有就直接 return
直到算出目標值時再把答案 return 出來
時間複雜度 O(n)
效率不會輸迴圈解
參考資料:
[One Punch 一拳搞定前後端面試] DAY-12 - 記憶化 | iT 邦幫忙 (不過他是用 java 寫的)
ZeroJudge Forum