Algorithm

題目

LeetCode 146 的名稱就叫 LRU Cache，算是教科書等級的題目，希望你可以實作一個 cache，在內部的 Cache Key 有著透過 LRU 演算法的淘汰機制（最久沒影使用的 Key 會優先淘汰）。

時間複雜度限制 get 和 set 都要 O(1)。

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

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

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

在第四篇提到費氏數列的公式解會遇到浮點數問題，只能精準算到 122 位。因為浮點數是利用二進位的小數來做儲存，對於非二進位的數字會有誤差。而且其儲存位數有上限，對於無理數的運算，超過一定的大小就會出現精確度問題。

所以這篇就要來簡單使用 Python 內建的 Decimal module 來拉高浮點數運算的精確度。

在第二篇介紹了費氏數列的矩陣解法，不過費氏數列其實是可以直接用公式算出第 n 項的值的，這邊就來介紹並推導一下公式解，順便幫自己複習一下數學 XD

上篇寫到費氏數列的矩陣解法來達成 $O(\lg n)$ 的時間複雜度，實際上可以再做一些變化來簡化計算。如果目標時間複雜度是 $O(\lg n)$，代表我們要能每次直接計算當 n 變成兩倍時的數值。

下面介紹的 Fast Doubling 方法就是這個例子。