考題：費氏數列 Problem: Fibonacci numbers · 演算法 Algorithms

考題：費氏數列

同一個數列四種算法：直接遞迴是指數時間，記憶化和迴圈是線性，矩陣快速冪只要 log n 次乘法。

解法

題目：算出 F(n)，其中 F(0) = 0、F(1) = 1、F(n) = F(n−1) + F(n−2)。例如 F(10) = 55。

1/50

正在呼叫正在回傳從快取直接回答

呼叫 fib(6)，它要再呼叫 fib(5) 和 fib(4)。目前 1 次呼叫。

四種解法算 n = 6

	F(n)	工作量	額外記憶體	Big O
直接遞迴	8	25 次呼叫	堆疊深度 6	O(φⁿ)
記憶化	8	11 次呼叫	快取 7、堆疊 6	O(n)
迴圈	8	6 次加法	2 個變數	O(n)
快速倍增	8	9 次乘法	2 個變數	O(log n)

大的 n

F(90) = 2880067194370816120(19 位數)

直接遞迴：9.32×10^18 次呼叫，跑不完
記憶化：179 次呼叫，遞迴深度 90
迴圈：90 次加法
快速倍增：21 次乘法，和迴圈算出的值相同

這裡數的是「大數運算」的次數，而 F(90) 有 19 位數：數字越大，每一次運算本身就越貴。大數乘法比加法慢得多，所以快速倍增實際上贏的幅度比次數看起來小，但 n 大時仍然遠遠領先。

亮起來的是這一步執行的程式碼

1function fibNaive(n: number): bigint {
2  if (n < 2) return BigInt(n);
3  return fibNaive(n - 1) + fibNaive(n - 2);
4}
5 
6function fibMemo(n: number, memo = new Map<number, bigint>()): bigint {
7  const hit = memo.get(n);
8  if (hit !== undefined) return hit;
9  const value = n < 2 ? BigInt(n) : fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
10  memo.set(n, value);
11  return value;
12}
13 
14function fibLoop(n: number): bigint {
15  let a = 0n, b = 1n;
16  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
17  return a;
18}
19 
20function fibDoubling(n: number): bigint {
21  let a = 0n, b = 1n; // F(k) and F(k + 1), from k = 0
22  for (let bit = 31 - Math.clz32(n); bit >= 0; bit--) {
23    const c = a * (2n * b - a); // F(2k)
24    const d = a * a + b * b;    // F(2k + 1)
25    if ((n >> bit) & 1) [a, b] = [d, c + d];
26    else [a, b] = [c, d];
27  }
28  return a;
29}

模型假設與範圍

Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

面試時從直接遞迴講起，自己指出重複計算：畫出呼叫樹，fib(n−2) 被算了兩次、fib(n−3) 三次……這就是動態規劃的起點。
接著給記憶化（由上而下）和迴圈（由下而上）兩個 O(n) 版本，並說明迴圈只需要 O(1) 空間。
被問到「n 是 10¹⁸ 怎麼辦」時，才拿出矩陣快速冪或快速倍增。

和其他主題的關係

由這些組成: 動態規劃分治與遞迴樹

時間與空間複雜度（Big O）

操作	平均	最差
直接遞迴 φ ≈ 1.618；同一個 fib(k) 被重算很多次	O(φⁿ)	O(φⁿ)
記憶化遞迴空間 O(n)：快取加上 n 層的呼叫堆疊	O(n)	O(n)
迴圈空間 O(1)	O(n)	O(n)
快速倍增／矩陣快速冪以運算次數計；大數乘法本身的成本另計	O(log n)	O(log n)

空間：O(1) – O(n)，迴圈與快速倍增只要兩個變數，遞迴版本要堆疊

Big O 實測：n 變大時步數怎麼長

數的是：大數運算次數（呼叫、加法或乘法）

	Big O	n = 64	n = 256	n = 1,024	成長倍數：實測（理論）
記憶化：呼叫	O(n)	127	511	2,047	×16 (×16)
迴圈：加法	O(n)	64	256	1,024	×16 (×16)
快速倍增：乘法	O(log n)	21	27	33	×1.6 (×1.7)

直接遞迴是指數成長，不在這張表裡；見上方的比較表。

和其他做法比

	直接遞迴：呼叫	記憶化：呼叫	迴圈：加法	快速倍增：乘法
n = 10	177	19	10	12
n = 20	21,891	39	20	15
n = 30	2,692,537	59	30	15
n = 40	331,160,281	79	40	18
n = 90	9.32×10^18	179	90	21

直接遞迴的呼叫次數是 2·F(n+1) − 1（小的 n 有實際跑過驗證），每多 1 就乘上約 1.618 倍：指數成長，所以不放進下面的 Big O 實測表。記憶化每個 n 只算一次、另外多一次查快取，所以是 2n − 1 次呼叫。

真實世界裡的它

爬樓梯（一次走 1 或 2 階有幾種走法）就是費氏數列換個說法。
「答案對 10⁹+7 取餘數」的變形：快速倍增每一步都取餘數，數字就不會變大。
任何線性遞迴（例如 F(n) = F(n−1) + 2F(n−3)）都能寫成矩陣，用同樣的快速冪在 O(log n) 算出來。

取捨與陷阱

用 32 或 64 位元整數：F(47) 就超過 32 位元、F(94) 超過 64 位元，會默默溢位。
記憶化遞迴的深度是 n：Python 預設上限 1,000 層，n 一大就 RecursionError。
用浮點數的比內公式（φⁿ/√5）：n 超過 70 左右就因為精度不足而算錯。

演算法