Optimization

終於來到最後一篇了，前面幾篇依序寫了各種不同費氏數列的寫法，包含：遞迴、迭代、矩陣、從矩陣衍生的Fast doubling、以及最後公式解和補充的精確版公式解。

從時間複雜度來看，從矩陣開始都是 $O(\lg n)$（如果我們把公式解內指數運算當作 $O(\lg n)$ 的話），那這三個哪個比較快呢？

這篇文章裡面用 c 比較了 fast doubling 和公式解，發現號稱常數時間複雜度的公式解，反而慢上很多，而且還需要考慮精確度問題。