# [演算法] Ch2 ~ Ch3
本章主要介紹演算法設計與分析的過程，並介紹如 big-O, big-Omega 等表示 running time 的標記。

## Intro
:::warning
沒錯，Ch1 太廢了，懶得介紹 >_<
:::

一般來說，演算法設計與分析大致可以分以下步驟：
1. **Formulate Problem**：
- 先定義好問題的 **Input**, **Output**
2. **Develop Algorithm**：
- 設計演算法
3. **Prove Correctness**：
- 證明演算法的正確性與穩定性
- **正確性**：可以找到正確的答案嗎？
- **穩定性**：每個 input、每次執行都能找出正確的結果嗎？
- 大多數的演算法證明都在這一步
4. **Analyze Complexity**：
- 利用 **Asymptotic Notation** 去分析演算法的**時間複雜度**

## Asymptotic notations
### Intro
**Asymptotic notations** 是一個可以簡化演算法 running time 表示的表示法，利用一些常用的函數，來描述 running time 函數的行為。常見的 asymptotic notations 有以下幾種：

| 種類 | 意義 |
| -------- | -------- |
| $f = O(g)$ | $\exists \ c,n_0:f(n) \le cg(n),n \ge n_0$|
| $f = o(g)$ | $\exists \ c,n_0:f(n) < cg(n),n \ge n_0$|
| $f = \Omega(g)$ | $\exists \ c,n_0:f(n) \ge cg(n),n \ge n_0$|
| $f = \omega(g)$ | $\exists \ c,n_0:f(n) > cg(n),n \ge n_0$|
| $f = \Theta(g)$ | $\exists \ c_1,c_2,n_0: c_1g(n)\le f(n) \le c_2g(n),n \ge n_0$|

**Asytotic notations** 的優點：把 low-order terms 和係數捨去，大幅簡化演算法複雜度分析

### Properties
- **Transitivity**：
- $f = O(g)$ and $g = O(h)$, then $f = O(h)$
- $f = \Omega(g)$ and $g = \Omega(h)$, then $f = \Omega(h)$
依此類推
- **Reflexivity**：
- $f = \Theta(f)$
- $f = O(f)$
- $f = \Omega(f)$
- **Symmetry**：
- $f = \Theta(g) \Longleftrightarrow g = \Theta(f)$
- **Transpose symmetry**：
- $f = O(g) \Longleftrightarrow g = \Omega(f)$
- $f = o(g) \Longleftrightarrow g = \omega(f)$

## 證明方式
下方是常見的演算法證明方式，可以參考一下：

## Stirling's approximation
:::warning
這個必看，去年期中考有考過，**歐姆巴**說的
:::
- Stirling formula：
$(\frac{n}{e})^n < n! < (\frac{n}{e})^n \sqrt{2\pi n}(1 + \frac{1}{11n})$
- **Stirling's approximation**：
$n! = \sqrt{2 \pi n}(\frac{n}{e})^n(1 + \Theta(\frac{1}{n}))$

## Fibonacci numbers
### 遞迴解

### 公式解
- 與**黃金比例**有關
- **黃金比例 $\phi$**：
- $\phi = \frac{1 + \sqrt{5}}{2}$
- $\hat{\phi } = \frac{1 - \sqrt{5}}{2}$ ($\phi$ 的共軛根)
- $x^2 = x + 1$ 的兩根為 $\phi$ 與 $\hat{\phi}$
- $F_i = \lfloor \frac{\phi ^i}{\sqrt{5}} + \frac{1}{2} \rfloor$

## 常見級數
- $\sum _{i = 1}^n \frac{1}{i} \simeq \ln n + \gamma,\ \gamma \simeq 0.557$
- $\sum_{i = 1}^n i2^i = (n - 1)2^{n+1} + 2$
- $\sum_{i = 1}^n \log i = \Theta(n \log n)$
- $\sum_{i = 1}^n i^d \log i = \Theta(n^{d+1} \log n)$