Python 費氏數列解法(二):矩陣解

上篇我們討論了費氏數列的各種基本解法。

原本我也以為 O(n) 的迭代解就已經是標準解法了,直到被大神朋友指正:

問費氏數列應該是想聽 $O(\lg n)$ 解法吧?

查了一下還真的有,這篇文章寫得蠻完整的,這篇會參考該篇文章來撰寫,但會用我自己的話以及 Python 寫出來。

哪來的矩陣?

$$
\begin{bmatrix}
F(n)\\
F(n-1)
\end{bmatrix} = \begin{bmatrix}
F(n-1) + F(n-2) \\
F(n-1)
\end{bmatrix} = \begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix} \begin{bmatrix}
F(n-1)\\
F(n-2)
\end{bmatrix}
$$

其實就是將上篇的尾遞迴方法及迭代法中每次的運算內容,使用矩陣乘法表達出來。

有了矩陣可以幹嘛(公式推導)

有了矩陣表示法,對於費氏數列第 n 項 $F(n)$ 就可以表示成:

$$
\begin{bmatrix}
F(n)\\
F(n-1)
\end{bmatrix} = \begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix} … \begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}\begin{bmatrix}
F(2)\\
F(1)
\end{bmatrix} = \begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^{n-2} \begin{bmatrix}
1\\
1
\end{bmatrix}
$$

兩邊同乘中間那個 1 1 1 0 的矩陣:

$$
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}
\begin{bmatrix}
F(n)\\
F(n-1)
\end{bmatrix} = \begin{bmatrix}
F(n+1)\\
F(n)
\end{bmatrix} = \begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^{n-1} \begin{bmatrix}
1\\
1
\end{bmatrix}
$$

又:

$$
\begin{bmatrix}
F(n)\\
F(n-1)
\end{bmatrix} = \begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^{n-1} \begin{bmatrix}
1\\
0
\end{bmatrix}
$$

把 $F(n+1)$ 和 $F(n)$ 開頭的兩行做合併之後可以得到更漂亮的寫法:

$$
\begin{bmatrix}
F(n+1) & F(n)\\
F(n) & F(n-1)
\end{bmatrix} = \begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^{n-1} \begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}
$$

得到最後的公式:

$$
\begin{bmatrix}
F(n+1) & F(n)\\
F(n) & F(n-1)
\end{bmatrix} = \begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^{n}
$$

矩陣的 n 次方真的可以 $O(\lg n)$ 嗎?

不同的例子不同,因為矩陣的乘法實際上並不會都是 $O(1)$,但是在這裡我們固定了矩陣的大小為 $2 \times 2$,只會對費氏數列的 n 做增長,因此矩陣乘法本身的複雜度並不會增長。

這邊有個名詞是快速冪,中文也許不好懂,英文就是 exponentiation by squaring,就是把高次方的 power 用 2 的次方去組合。或著是說,用其二進位時數值是 1 的位元來做組合。
因此算某數的 n 次方,我們只需要進行 $O(\lg n)$ 次計算即可。

舉個簡單的例子,當計算 x 的 23 次方時,我們知道 23 的二進位可以表示成 10111,因為:

$$
23 = 2^4 + 2^2 + 2^1 + 2^0
$$

所以實際上我們只要計算:

$$
x^{23} = x^{2^4 + 2^2 + 2^1 + 2^0} = x^{16}x^4x^2x
$$

其中四個數值的次方計算為:

  • $x^{16} = x^8x^8$
  • $x^{8} = x^4x^4$
  • $x^{4} = x^2x^2$
  • $x^{2} = xx$

時間複雜度空間複雜度都是 $O(\lg n)$

拿來應用在矩陣上,就是所謂矩陣快速冪

說了這麼多,給我 code 吧

這裡參考了 leetcode 的官方解法

def fibonacci(n):
    A = [[1, 1], [1, 0]]
    power(A, n-1)
    return A[0][0]

def power(A, n):
    if n < 2:
        return A
    q, r = divmod(n, 2)
    power(A, q)
    multiply(A, A)
    if r != 0:
        multiply(A, [[1, 1], [1, 0]])
        
def multiply(A, B):
    x = A[0][0] * B[0][0] + A[0][1] * B[1][0]
    y = A[0][0] * B[0][1] + A[0][1] * B[1][1]
    z = A[1][0] * B[0][0] + A[1][1] * B[1][0]
    w = A[1][0] * B[0][1] + A[1][1] * B[1][1]

    A[0][0] = x
    A[0][1] = y
    A[1][0] = z
    A[1][1] = w

因為要進行矩陣運算,我們必須另外實作相關 code,所以才多了 powermultiply 兩個 function。
當然,也可以直接使用 numpy:

def fibonacci(n):
    # 但我自己測試,這個會有精確度問題
    A = np.array([[1, 1], [1, 0]])
    return np.linalg.matrix_power(A, n-1)[0, 0]

以上就是費氏數列的 $O(\lg n)$ 矩陣解法。

不過其實這個方法還能進一步改善,就留到下一篇再說明吧。

參考資料: