遞迴函式計算費波那契數的時間複雜度分析
大家好，不知道大家今天有沒有吃飽呢？
剛入門程式設計，學到「遞迴」操作的時候，老師們都很喜歡舉「費波那契數」的計算為例。以下，我也用 JavaScript 程式碼展示一下費波那契數的計算：
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(10)); // 55這樣的遞迴函式看起來是沒有問題的，但是您可以把 45 以上的數字帶入這個函式試試看。執行的時候，您可能會以為程式卡住了，其實並沒有卡住，只是計算量會變得非常驚人！
function recursiveFibonacci(n) {
if (n <= 1) return n;
return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
}
function logFibonacciWithTime(n) {
const label = `f(${n})`;
console.time(label);
const result = recursiveFibonacci(n);
console.timeEnd(label);
console.log(`${label} = ${result}`);
}
logFibonacciWithTime(35);
logFibonacciWithTime(40);
logFibonacciWithTime(41);
logFibonacciWithTime(42);
logFibonacciWithTime(43);
logFibonacciWithTime(44);
logFibonacciWithTime(45);
logFibonacciWithTime(46);
logFibonacciWithTime(47);
logFibonacciWithTime(48);
logFibonacciWithTime(49);
logFibonacciWithTime(50);bun index.js
[55.70ms] f(35)
f(35) = 9227465
[386.84ms] f(40)
f(40) = 102334155
[631.33ms] f(41)
f(41) = 165580141
[1016.06ms] f(42)
f(42) = 267914296
[1.70s] f(43)
f(43) = 433494437
[2.72s] f(44)
f(44) = 701408733
[4.32s] f(45)
f(45) = 1134903170
[6.97s] f(46)
f(46) = 1836311903
[11.27s] f(47)
f(47) = 2971215073
[18.26s] f(48)
f(48) = 4807526976
[29.58s] f(49)
f(49) = 7778742049
[61.63s] f(50)
f(50) = 12586269025我想像的結果是這些計算都可以在幾毫秒的時間搞定啊，為什麼跟我想的差了幾百上千倍呢？
我們試著分析看看它的時間複雜度：
假設 n 是一個大數，我們計算 fibonacci(n - 2) 的需要 t 單位的時間，並且假設計算 fibonacci(n - 1) 需要 a 倍的 t 單位時間 at。
那麼計算 fibonacci(n) 就是需要 at + t 的時間，而計算 fibonacci(n + 1) = fibonacci(n) + fibonacci(n — 1) 所需的時間就是 (at + t) + at 的時間。
計算 fibonacci(n + 1) 的時間比上計算 fibonacci(n) 的時間會等於計算 fibonacci(n) 的時間比上計算 fibonacci(n — 1) 的時間。所以：
[(at + t) + at] : (at + t) = (at + t) : at
=> (at + t)² = (2at + t) * at
移項之後可以得到 a²t² — at² — t² = 0
由於 t 是常數，我們可以把 t² 除掉，變成 a² — a — 1 = 0, a > 0。解方程式就可以得到 a = (1 + sqrt(5)) / 2 = 1.618034…. 這正好是黃金分割率 φ。
每當要計算的費波那契數增加 1 ，計算的時間就會增加 φ 倍，所以用遞迴的方法計算費波那契數的時間複雜度就是 O(φn)。計算時間呈現指數級別增長的算法是相當糟糕的。
沒有數據的話您可能感覺不出來，我的電腦執行以上的程式計算 fibonacci(50) 的時間是 62 秒左右，那麼如果要計算 fibonacci(100) 的話，理論上可能要花費的時間是 φ⁵⁰ * 62 秒。您可以按計算機算算看，大約是五萬至七萬「年」左右的時間呢，嚇人吧？
