斐波那契數列定義
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n≥2)
數列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...
三種實現方式深度對比
1. 遞歸實現（教學用，生產禁用）
public int fibRecursive(int n) {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
| 指標 | 表現 |
|---|
| 時間複雜度 | O(2^n) 指數級爆炸 |
| 空間複雜度 | O(n) 棧深度 |
| 問題 | 大量重複計算、棧溢出風險、n>40 極慢 |
| 適用場景 | 僅教學演示、n 極小（<20） |
2. 迭代實現（時間換空間，推薦通用）
public int fibIterative(int n) {
if (n <= 1) return n;
int a = 0, b = 1, result = 0;
for (int i = 2; i <= n; i++) {
result = a + b;
a = b;
b = result;
}
return result;
}
| 指標 | 表現 |
|---|
| 時間複雜度 | O(n) |
| 空間複雜度 | O(1) 僅三個變量 |
| 優勢 | 無棧溢出、內存極小、速度快 |
| 適用場景 | 單次查詢、內存受限環境、嵌入式系統 |
3. 緩存實現（空間換時間，高頻查詢首選）
public class FibonacciCache {
private static final List CACHE = new ArrayList<>();
private static final int MAX_N = 92; // Long 最大 F(92)=7540113804746346429
static {
CACHE.add(0L); // F(0)
CACHE.add(1L); // F(1)
for (int i = 2; i <= MAX_N; i++) {
CACHE.add(CACHE.get(i-1) + CACHE.get(i-2));
}
}
public static long get(int n) {
if (n < 0 || n > MAX_N) throw new IllegalArgumentException("n 超出範圍 [0, " + MAX_N + "]");
return CACHE.get(n);
}
}
| 指標 | 表現 |
|---|
| 預計算時間 | O(MAX_N) 一次性 |
| 查詢時間 | O(1) 直接下標訪問 |
| 空間複雜度 | O(MAX_N) 約 93 個 Long |
| 適用場景 | 高頻重複查詢、生命周期長、作為工具類常駐內存 |
溢出處理與類型選擇
| 類型 | 最大 n | 最大值 |
|---|
| int (32位) | 46 | 1,836,311,903 |
| long (64位) | 92 | 7,540,113,804,746,346,429 |
| BigInteger | 無限制 | 受內存限制 |
建議：通用場景用 long 覆蓋 n≤92；大數用 BigInteger。
完整測試代碼
public class FibonacciTest {
public static void main(String[] args) {
int n = 46; // int 最大安全值
System.out.println("遞歸: " + fibRecursive(n)); // 1836311903
System.out.println("迭代: " + fibIterative(n)); // 1836311903
System.out.println("緩存: " + FibonacciCache.get(n)); // 1836311903
// 性能對比
long start = System.nanoTime();
fibRecursive(40); // 慢
System.out.println("遞歸 40 耗時: " + (System.nanoTime() - start) / 1e6 + " ms");
start = System.nanoTime();
fibIterative(40);
System.out.println("迭代 40 耗時: " + (System.nanoTime() - start) / 1e6 + " ms");
start = System.nanoTime();
FibonacciCache.get(40);
System.out.println("緩存 40 耗時: " + (System.nanoTime() - start) / 1e6 + " ms");
}
// 方法定義同上...
}
算法選擇決策樹
需要斐波那契數？
│
├─ 單次查詢、n 不大（<1000） → 迭代法（O(n) 時間，O(1) 空間）
│
├─ 高頻查詢、固定範圍 → 靜態緩存預計算（O(1) 查詢，O(n) 空間）
│
├─ 教學/驗證數學定義 → 遞歸（僅 n<20）
│
└─ 超大 n（>10000） → 矩陣快速冪 O(log n) / 公式法（浮點誤差）
矩陣快速冪優化（補充：O(log n)）
// [F(n+1) F(n) ] [1 1]^n
// [F(n) F(n-1)] = [1 0]
// 利用矩陣快速冪 O(log n) 計算，適合極大 n
// 代碼略，核心：矩陣乘法 + 二分冪
總結
斐波那契數列看似簡單，卻蘊含遞歸、動態規劃、備忘錄、矩陣冪等核心算法思想。沒有最好的算法，只有最適合場景的算法：單查用迭代，高頻用緩存，極大 n 用矩陣冪。理解時空權衡，才是算法工程化的核心。
