想更快算出費氏數列嗎？來看看矩陣快速冪吧！
筆者我年輕的時候（？）對演算法很有興趣，刷了不少 Online Judge 題目（那時最常玩 ZeroJudge 跟 台中女中程式解題系統），因為當時也才高中，所以當然不是為了準備面試，就只是當做鍛鍊腦力這樣XD
而今天我要跟大家分享我個人覺得最有趣的演算法之一：矩陣快速冪。我知道有些人聽到「矩陣」就先倒退三步，再看到「快速冪」這不知所云的東西可能就直接把網頁關了，反正不能更快算出費氏數列好像也無所謂XD
但其實今天會用到的數學都很基本，而且我還畫了一些精美的圖，以大家的聰明才智應該沒什麼問題才是
O(n) 的費氏數列算法
平常在算費氏數列第 n 項時常會這樣寫：先設定好 f[0] = 0 跟 f[1] = 1 後，由這兩項不斷往後加，直到算出第 n 項
因為這樣一項一項往後加總共要做 n — 1 次加法，需要的時間基本上跟 n 成正比，因此時間複雜度是 O(n)。雖然 O(n) 已經比「用遞迴又不做快取」快很多，但如果數字很大，譬如說要算出第 10000 項，那還是比較費工一點
說了這麼多，今天就是要來跟大家介紹一個 O(log(n)) 時間複雜度的演算法，讓大家可以更快算出 fib(n)
快速冪
首先來講講快速冪，快速冪是一種用來計算「x 的 n 次方」的演算法。直覺上 x^n 就是把 x 連乘 n 次，所以程式碼常會寫成這樣，複雜度是 O(n)
但除了直接爆乘一波之外，其實還有另一種更有效率的方法，就是利用指數乘法的定理，把 x^(2k) 寫成 (x^k)²
什麼意思呢？譬如說我最終目標是算出 x¹⁶，那就先算出 x⁸ 再平方。那我要怎麼算出 x⁸ 呢？那就是先算出 x⁴ 再平方。就這樣一直推下去，那就只需要經過 x²、x⁴、x⁸、x¹⁶ 共四次平方，就可以得到 x¹⁶，不用傻傻的連乘 16 次
那如果遇到奇數怎麼辦呢？譬如說我要算 x¹⁷ 次方，那就是先用上面的方法算出 x¹⁶ 次方，最後再乘上一個 x 就行啦
概念大致上是這樣，寫成程式的話就是先判斷奇偶，再根據上面的公式拆開去做遞迴
因為在計算過程中次方數會不斷的被砍半，就連計算 x¹⁰⁰⁰ 也只需要經過十六次乘法，所以複雜度是 O(log(n))
概念都了解後可以去解解看 Leetcode 上的 Pow(x, n) 跟 Super Pow，快速冪開下去應該很容易可以拿到好成績～
學會了快速冪，然後呢？
啊不對啊，快速冪是用平方來解決乘法問題，但費氏數列不是用加的嗎，干快速冪什麼事？
雖說費氏數列是用加的沒錯，但其實也可以用矩陣乘法來算哦～
這邊簡單複習一下高中學過的矩陣乘法，當兩個矩陣在相乘時，A 矩陣的第一列(Row)會跟 B 的第一行(Column)做內積，然後把結果放到 C 矩陣的第一行第一列
而其他欄位也是一樣，「A 的第 i 列」會跟「B 的第 j 行」做內積，然後放到 「C 矩陣的第 i 列(Row) 第 j 行(Column)」
用矩陣乘法計算費氏數列
除了用加的之外，其實費氏數列還有另外一種計算方式，那就是「費氏數列的第 n 項會等於 A 矩陣的 (n-1) 次方後，左上方的那個元素」
為了方便，我們把 [[1, 1] [1, 0]] 叫做 A 矩陣，至於他是怎麼推導出來的比較複雜，在這邊只要記得下面的公式就好了
譬如說要計算 fib(6)，那就把 A 矩陣連乘五次，就可以得到 fib(6) = 8，利用這個特性，我們就可以把費氏數列從加法問題變成乘法問題！
以後要計算 fib(n) 就用下面這條公式：先算出矩陣 A 的 (n-1) 次方，然後取左上角的值（[0][0]）就可以了～
矩陣乘法 + 快速冪 = 矩陣快速冪
接著就是要把快速冪跟矩陣乘法湊在一起，雖然矩陣乘法看起來比較複雜，但畢竟次方就是連乘而已，所以矩陣的次方也可以適用快速冪的原理，也就是把 A^(2k) 寫成 (A^k)²
因此，到這邊我們已經掌握了兩個關鍵：
- 用快速冪在 O(log(n)) 時間內計算出 A^(n-1)
- 從 A^(n-1) 得到 fib(n) 的值
只要把兩個綜合起來，就可以用快速冪在 O(log(n)) 時間內算出 fib(n) 了～
實作矩陣快速冪
概念上都了解後就來實作吧！
首先是 JS 並沒有內建矩陣乘法，所以要自己實作一個 multiply 函數，之後會用在矩陣之間的相乘、平方。而實作的方式也很簡單，就是根據矩陣乘法的公式把每個元素都算出來而已XD（忘記了可以看上面 A x B = C 的圖）
接下來的 pow_of_A(n) 是整段程式碼最核心的部分，用來 快速計算 A^n
因為只是把普通乘法換成矩陣乘法，所以實作也跟普通的快速冪一樣：先判斷 n 是奇數偶數，奇數的話就把 n 拆成 2k + 1，偶數的話則是拆成 2k，這樣就可以在 O(log(n)) 時間內計算出 A 矩陣的 n 次方
有了 pow_of_A(n) 之後，最後一步就是把上面這條公式寫成程式碼，這樣一來就可以得到 O(log(n)) 複雜度的 fib(n) 了～
把程式碼實際丟到 Leetcode — Fibonacci Number 成績也還不錯，可惜這題的 n 最大只到 30，所以 O(n) 跟 O(log(n)) 的差距並不大，不然矩陣快速冪開下去就快個一百倍也是有可能的
總結
關於矩陣快速冪的概念及實作就講到這，希望大家在看完這篇文章後至少都能了解「怎麼用快速冪計算次方」，至於「用矩陣快速冪計算費氏數列」的部分比較難一點XD，如果看了幾遍還是不懂可以加我的 Telegram，我一定會想辦法講到你懂的～
另外，除了文中提到的 Pow、Super Pow、Fibonacci Number 可以玩玩看之外，Climbing Stairs 跟 N-th Tribonacci Number 也是跟費氏數列有關的題目，雖然題目給的 n 不大，所以用 O(n) 的迴圈解也可以，但想練練矩陣快速冪的話可以自己寫寫看哦～
後記
其實我很久之前就想寫這個題目了，但一直沒有把握要怎麼把這麼偏數學的演算法寫好，怕大家一看到公式、矩陣就頭痛，所以也算是我給自己的一個挑戰XD，希望大家喜歡這個題目啦～
