###### tags: `algorithm`, `note`, `test`, `thu`

# Algorithm Final review

## 1. 定義
#### 問題(An instance of problem):
- An ***instance of problem*** consist of all inputs needed to compute a solution to the problem.
#### 演算法(Algorithm):
- Any well-defined computation procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.

#### 正確的演算法(Correct Algorithm):
- An algorithm is said to be correct if for every input instance, it halts with the correct output.

## 2. 執行時間(Running time)
#### 計算原則:
- 因為我們每個計算機的性能都不相同，核心數也一樣，因此我們在計算執行時間時會以steps(約等於一行指令)為計算的標凖。

#### 符號(Asymptotic notation):
- $O$: 問題的worst-case bound。
- $\Omega$: 問題的best-case bound。
- $\Theta$: 問題的tight-bound。

#### 計算方法(通常針對遞迴的題型)
- 代入法: 猜解，並且試著帶入。
- 畫樹: 依據計算原則列出每一層遞迴的成本，並且使用公式相加。
- Master theorem: 使用大師定理判斷。(有三種case)

## 3. 排序
### A. 常見的排序演算法:
#### 插入排序(Insertion Sort)
#### 合併排序(Merge Sort)
#### 堆排序(Heap Sort)
#### 快速排序(Quick Sort)

### B. 基於比較的排序演算法限制
- 因為是使用比較進行排序的，因此每比較次就可以想成樹(tree)分支了一次，因此最後葉子總數就會是元素的數量($n!$)
- 而樹的高度就會是$O(lgn)$。
- 因此Worst-case就不可能比$O(nlgn)$還要快。

### C. 線性排序(需滿足特定條件)
#### 數數排序(Counting Sort)
- $k$為數數的範圍，而$n$為排序元素的數量
- 限制: 需為正數(介於$0$~$k$之間)
- Worst-case: $O(k + n)$
#### (Radix Sort)
- $d$為最大可能的位數，$k$為每一位數可能數字的數量。
- 限制: 需為正數
- Worst-case: $\Theta(d(n+k))$
#### (Bucket Sort)
- Stable
- Not in-place
- Worst-case: $\Theta(n)$

## 4. 二分搜尋樹(Binary Search Tree)
#### Traversal
- Preorder: 前序拜訪
- Inorder: 中序拜訪
- Postorder: 後序拜訪
#### 操作
- 原則: 左小右大
- 新增、刪除、找下一個

## 5. 動態規劃(Dynamic Programming)
#### 前提
- 最佳子結構: 大的答案可用小的答案組合而成。
#### 䇿略
- Tabulation: 利用連續的資料容易計算的物性，事先把結果計算出來
- Memoization: 充分利用已經計算過的資料，對已經計算過的資料進行快取。

#### 常見題型
- 矩陣鏈: Matrix Chain Multiplication
- 最長子序列: Longest Common Subsequence

## 6. 貪婪演算法(Greedy Algorithm)
#### 前提
- 除了最佳子結構之外，我們還需要***Greedy Choice***的存在。

#### 策略
- 每次都選出當下的最佳解，靠著***Greedy Choice***的特性得出Global Optimal。

#### 常見題型
- 背包問題(小數): 如果是整數，則只能使用DP。
- Huffman Code

## 7. 圖論
#### 探索
- 廣度優先搜尋(Bread-first Search): $O(V + E)$
- 深度優先搜尋(Depth-first Search): $O(V + E)$

#### 最小生成樹(Minimum spanning tree, MST)
- Prim's Algorithm: $O(E+VlogV)$ or $O((E+V)logV)$
- Kruskal's Algorithm: $O(ElogV)$

#### 最短距離
- 只要負Cycle出現，則無解。(呷賽)
##### - 單點:
- 邊長為正: Dijkstra's Algorithm: $O(V^2 + E) => O(E + VlogV)$
- 邊長可為負: Bellman-Ford Algorithm: $O(VE)$

##### - 所有點:
- Floyd-Warshall
- Johnson's algorithm for sparse graphs
- Reweighting
- Apply Dijkstra's algorithm
- Recover the weight

## 8. P, NP, NPC
#### P: 多項式時間內 ***解答*** 完成
#### NP: 多項式時間內 ***驗証*** 答案完成
#### NP-Complete:
- Traveler Salesman Problem(TSP): 給定一系列城市和每對城市之間的距離，求解訪問每座城市一次並回到起始城市的最短迴路。

- Circuit Satisfiability Problem(Circuit-SAT):