白板程式設計：斐波那契數列實戰#

以斐波那契數列為例，展示如何在面試中從暴力解逐步優化到最優解。

解法演進#

1. 暴力遞迴 $O(2^n)$#

最直觀的解法，直接定義 $f(n) = f(n-1) + f(n-2)$：

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

存在大量重複計算。例如計算 $f(5)$ 需要計算 $f(4)$ 和 $f(3)$，而計算 $f(4)$ 時又要計算一次 $f(3)$。當 $n=40$ 時，程式執行速度將變得極慢。

2. 記憶化遞迴 $O(n)$#

加上快取，避免重複計算：

def fib(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

3. 動態規劃 $O(n)$#

正推方式，只保留前兩個狀態：

def fib(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

4. 矩陣快速冪 $O(\log n)$#

斐波那契數列求第 $n$ 項的最優解法是矩陣快速冪，時間複雜度為 $O(\log n)$。

矩陣快速冪原理#

構造狀態矩陣#

找到常數矩陣 $M$，使得：

$$ \begin{bmatrix} F_n \ F_{n-1} \end{bmatrix} = M \times \begin{bmatrix} F_{n-1} \ F_{n-2} \end{bmatrix} $$

根據斐波那契定義：

  • $F_n = 1 \cdot F_{n-1} + 1 \cdot F_{n-2}$
  • $F_{n-1} = 1 \cdot F_{n-1} + 0 \cdot F_{n-2}$

得到常數矩陣：

$$ M = \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix} $$

轉化為冪運算#

展開遞推：

$$ \begin{bmatrix} F_n \ F_{n-1} \end{bmatrix} = M^{n-1} \times \begin{bmatrix} F_1 \ F_0 \end{bmatrix} $$

求解 $F_n$ 轉化為求解 $M^{n-1}$，套用快速冪演算法即可達到 $O(\log n)$。

升維思想：在一維遞推中只能達到 $O(n)$。引入矩陣後，利用數學結構「摺疊」計算過程，實現指數級加速。

快速冪演算法#

核心思想#

利用 $x^n = x^{n/2} \times x^{n/2}$ 的性質，將規模減半。

二進位制迭代法（推薦）#

將 $n$ 視為二進位制串。例如 $x^{10}$，$10$ 的二進位制是 1010，即 $x^8 \times x^2$。

double myPow(double x, int n) {
    long long N = n;
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }

    double result = 1.0;
    double current_product = x;

    while (N > 0) {
        if (N & 1) {  // 當前位元是 1
            result *= current_product;
        }
        current_product *= current_product;  // 權重翻倍
        N >>= 1;  // 處理下一位
    }

    return result;
}

位元運算技巧：

  • n & 1 判斷奇偶（等價於 n % 2 == 1）
  • n >> 1 右移一位（等價於 n / 2）

面試中的 Clarification#

遇到 pow(x, n) 這類題目，務必先確認邊界條件：

  • $n$ 可以是負數嗎？
  • $x$ 可以是 $0$ 嗎？（$0$ 的負數次方會導致除以零）
  • 需要處理整數溢位嗎？（如 $n = \text{INT_MIN}$ 時，$-n$ 會溢位）

Clarification 比直接寫出程式碼更重要。這展示了你的工程思維與嚴謹性。

遞迴模板#

面試中使用遞迴時，遵循以下四步驟：

  1. Terminator：終止條件
  2. Process：處理當前層邏輯
  3. Drill Down：下探到下一層
  4. Clear Status：清理當前層狀態（若需要）

能夠看出程式碼的「壞味道」並進行重構，是工程師進階的必經之路。例如將 n % 2 優化為 n & 1，不僅是效能提升，更是對底層邏輯理解的展現。

Backward 面試準備