在上篇我們討論了費氏數列的各種基本解法。
原本我也以為 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，所以才多了 power 和 multiply 兩個 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)$ 矩陣解法。
不過其實這個方法還能進一步改善，就留到下一篇再說明吧。