終於來到最後一篇了，前面幾篇依序寫了各種不同費氏數列的寫法，包含：遞迴、迭代、矩陣、從矩陣衍生的Fast doubling、以及最後公式解和補充的精確版公式解。
從時間複雜度來看，從矩陣開始都是 $O(\lg n)$（如果我們把公式解內指數運算當作 $O(\lg n)$ 的話），那這三個哪個比較快呢？
這篇文章裡面用 c 比較了 fast doubling 和公式解，發現號稱常數時間複雜度的公式解，反而慢上很多，而且還需要考慮精確度問題。
所以，Fast doubling 勝。
但在 Python 又是如何呢？前幾篇我們都在講 Python，因此所以我寫了一段 Python code 來做實驗，把這幾篇提到的方法全部一起比較了一下。
實驗結果
對照如下：
- fib_binet: 公式解（Decimal 實作版本，補充篇），時間複雜度 $O(\lg n)$
- fib_fast_double: 遞迴版本的 fast double（第三篇），時間複雜度 $O(\lg n)$
- fib_fast_double_iter: 迭代版本的 fast double（第三篇），時間複雜度 $O(\lg n)$，最快的一個
- fib_matrix: 矩陣解法（第二篇），時間複雜度 $O(\lg n)$
- fib_iterative: 迭代解法（第一篇），時間複雜度 $O(n)$
- fib_lru: 遞迴解法，加上 lru_cache（第一篇），時間複雜度 $O(n)$
看看那個公式解浮在那個地方 XDDD
可能是 Decimal 把精確度開高之後效能犧牲太多了，因為常數部分被拉了很高，曲線看起來很接近 $O(1)$。
如果刪掉公式解之後，其他解法的結果如下：
相較其他每個解法都跑得快多了，即便是 $O(n)$ 的基本遞迴和迭代也是，有趣的是，使用 lru_cache 的遞迴速度仍然比相同複雜度的迭代版本要來得慢不少，我猜也許是因為重複 call function 並處理 cache 所造成的的 overhead 在 Python 內還是不小，所以能不要偷懶還是不要偷懶，就改寫成 iterative 吧。
矩陣解和 fast double 雖然都是 $O(lg n)$，但兩者常數也是插上很多，雖然增長速度都很慢，但 fast_double 快上一截，而且又以迭代版本的比遞迴版本的更快。
最後附上實驗的原始碼：
測試 CPU 是 4.00GHz 的 i7-6700K，作業系統是 ubuntu 18.04，Python 3.9.1。
後記
拖稿了很久，終於來完成這系列文章了。
原先只打算寫個兩篇，沒想到越深入研究就越拆越多篇出來。其實費氏數列相關的討論還有很多，也有負數、無理數甚至複數的推廣，但後面就是數學系的事情了，對於工數只有線性代數和一點點微分方程基礎的我還是先在此打住好了 XD
可以來寫最近學的其他東西了～一坑開完又是一坑，這個系列實在有點解題+興趣導向，下次來寫點更實用的好了。