Fibonacchi Sequence
===
本篇：https://hackmd.io/@IncredibleCactus/SkRGbcMmp
## 定義
#### 費波那契數列

\begin{equation*}
F_0 = 0, \ F_1 = 1, \ F_n = F_{n-1} + F_{n-2} \ \ (n ≥ 2)
\end{equation*}

## 遞迴
### 想法
數列的公式看起來很遞迴。對於傳入的 $0$ 和 $1$ 回傳 $F_0$ 和 $F_1$，否則回傳 $F_{n-1}+F_{n-2}$。

### Code

def fibonacci(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(7)) # should be 13

### 複雜度
但遞迴的複雜度如何？ 經過測試 $n$ 大約每增加 $10$，時間會變成約 $122$ 倍。實際上消耗的時間約為 $1.618^n$，這個複雜度肯定是不行的，算 100 項十萬年都算不完，用手算都比較快。那要如何改進呢？

### 優化
我們可以開一個陣列計算第 $i$ 項有沒有被算過。如果有，那就直接拿陣列裡的東西來用，如果沒有，就計算出來後丟到陣列裡。這樣的複雜度就變成 $O(n)$ 了。

## $O(n)$
### 想法
既然我們可以透過第零項和第一項得出第二項，那我們可不可以透過第一項和第二項算出第三項呢？當然可以。同理，當我們有第 $n-2$ 項和第 $n-1$ 項，我們就能算出第 $n$ 項。

### Code

def fibonacci(n):
    a, b = 0, 1
    for i in range(0, n):
        b = a + b
        a = b - a
    return a
print(fibonacci(8)) # should be 21

### 複雜度
迴圈跑了 $n$ 次，算出下一項 $O(1)$，所以總共 $O(n)$。

## $O(log n)$
### 想法
考慮一個 2x1 的矩陣

\begin{equation*}
F_n =
\begin{pmatrix}
a_{n} \\
a_{n+1}
\end{pmatrix}
\end{equation*}

若有辦法找出 2x2 矩陣 A 使得

\begin{equation*}
AF_n = F_{n+1} =
\begin{pmatrix}
a_{n+1} \\
a_{n+2}
\end{pmatrix}
\end{equation*}

則有

\begin{equation*}
F_n = A^nF_0 = A^n
\begin{pmatrix}
0 \\
1
\end{pmatrix}
\end{equation*}

我們不難求出 $2\times2$ 矩陣 $A$ 為

\begin{equation*}
A =
\begin{pmatrix}
0 & 1 \\
1 & 1
\end{pmatrix}
\end{equation*}

\begin{equation*}
AF_n =
\begin{pmatrix}
0 & 1 \\
1 & 1
\end{pmatrix}
\begin{pmatrix}
a_{n} \\
a_{n+1}
\end{pmatrix} =
\begin{pmatrix}
a_{n+1} \\
a_{n+2}
\end{pmatrix} =
F_{n+1}
\end{equation*}

因此，我們可以算出矩陣 $A$ 的 $n$ 次方，從而得到第 $n$ 項。那我們要如何用 $O(log n)$ 的複雜度算出 $A$ 的 $n$ 次方呢？用快速冪就可以在 $O(log n)$ 的時間內算出來。
我懶得寫了所以請參考 https://cp.wiwiho.me/pow/ 的概念。

### Code

def matrix_multiply(a, b):
    result = [[None, None], [None, None]]
    result[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0]
    result[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1]
    result[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0]
    result[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1]
    return result

def fast_fibonacci(n):
    t = [[0, 1], [1, 1]]
    A = [[0, 1], [1, 1]]
    while (n >= 1):
        if n % 2 == 1:
            A = matrix_multiply(A, t)
        t = matrix_multiply(t, t)
        n = n // 2
    return A[0][0]

print(fast_fibonacci(9)) # should be 34

### 複雜度
快速冪 $O(log n)$，將 $A^n$ 乘上 $F_0$ 需要 $O(1)$。總時間複雜度 $O(log n)$。