費波納契數列的最佳計算複雜度 O(logn) 實現及推導（fibonacci sequence in cpp）
因為最近在解 Leetcode 的 91. Decode Ways ， 要用到 Fibonacci sequence 來解，就我所知上次解 70 . Climbing Stairs 的時候， 用 recursive 求解 Fibonacci sequence 的時候會 TLE。 （所以我就偷懶跑去用 Python3 解大數） 這次再遇到應該是要進步了xDDD 正文開始： Fibonacci sequence 會長這個樣子： 根據基本定義，第 N 個 Fibonacci value 等於前兩個 Fibonacci value 相加， 我們便可以得到公式： 得到公式以後把它擴展成 轉移矩陣 M 的形式， 因為我們把前兩項當作初始值，所以 轉移矩陣 M 的指數會減二： 所以我們現在只要計算 M 的 (n-2) 次方就能得到第 N 個 Fibonacci value。 （左上角的 M00 會等於 第N個 Fibonacci value ） 此時的計算複雜度為： O(n) 以第 45 個 value 值來比較，此方法已經比遞迴快很多了xD 但是我還要教你一個威力加強版外掛：平方求冪 （左岸又稱快速冪 or double-and-add ） 我們在這裡要用平方求冪去優化轉移矩陣 M。 平方求冪的想法是把任何高階指數都化為與指數二有關的指數和， 屁話一堆直接看數學比較快： 如果你說 n 是 odd 怎麼辦？ 啊不簡單？直接減一再乘回去R~： 這樣的好處是能大大的減少計算量，數學意義上來說是二分搜尋法， 以找 n = 16 舉例， 沒有平方求冪的版本會很老實地計算十五次乘法， 而有平方求冪外掛的版本會跳著算： 像是圖中有幾個節點，就計算幾次， 每次都是跟自己相乘，所以實際上只要算黃色螢光筆那條路徑， 不必考慮其他條黑色路徑。 由此可以 16 = 2^4，所以有 4 個節點，只需計算 4次。 此時又可推導出 計算複雜度為： O(logn) （log 以 2 為底。） 用 C++ 實現的程式碼我放在 這裡 有興趣的可以直接拿來用，不用再造車輪了xD 感謝各位