### algorithm overview

- [algorithm overview](https://hackmd.io/fRiBP7u1S_yE8k_5GxAPnQ?both)
- [complexity](/6LLQEyeaRjCahtEV3ov7lA)

## graph
### graph
- [graph](/i0FmQWK_SlqKRVYh0wBKvg)
### MST
- [prim](/D3YP4moJSraEm--lzp3jLg)

### shortest path
- [floyd-warshall](/oI7JbjBuQdWOR3e5_wc6fw)

## NP related
[Theory of NP-Completeness](/qm8Hauf4Tnmi8oOd_Euo5A)

## other
- [huffman_coding](/asv43zitSnmddCu_GDkvDQ)

## 期末
### 計畫/開銷的最佳化
點 $i,j$ => 代表 (計畫,開銷)，開銷可為 0，如果開銷過大，則轉移的邊權重為 0，意味著用光，無收益。
邊 $a$ => 代表收益

有兩虛擬點 $S,T$，代表開始結束
一條路徑的邊收益總和，就是一種方法。

### 最長共同子序列
字串 $a,b$
其中，$a,b$ **最長的** **不一定連續的** **共有的** 字串 LCS 是什麼？LCS 非唯一。

$L_{i,j} = \begin{cases}
x_i = y_i \rightarrow 1 + L_{i-1,j-1} \\
x_1 \neq y_i \rightarrow \max(L_{i-1,j}, L_{i,j-1})
\end{cases}$

可以畫成 array_2d，圖中可以看到有幾個 LCS。
$a = x$ 軸
$b = y$ 軸
$x=0, y=0$ 被跳過，從 $1$ 開始 ，不然 $a,b$ 會搶 $[0][0]$

### NP 問題
#### **P** => $O(n^c)$ 內算完
排序問題 (Sorting) $O(n \log n)$
最短路徑
最長共同子序列 (LCS) $O(nm)$
最大流

#### **NP** => $O(n^c)$ 內驗證
關係: $P \subseteq NP$
0-1 背包 (0-1 Knapsack)

#### **NP-Complete (NPC)** => 任何 NP 都能在 $O(n^c)$ 內變成 NPC 的問題
關係: $NPC \subseteq NP$
>人類尚未解出任何 NPC 問題的多項式時間演算法，只證明他是 NPC。
所有 NPC 問題之間都存在「多項式歸約（Polynomial-Time Reduction）」的關係
把一個 NP 問題 A，快速轉換（只花多項式時間）成另一個問題 NPC 的輸入，使得解 NPC 可以幫你解出 A。

著色問題 (Graph Coloring)
旅行銷售員問題 (TSP)
邏輯滿足問題 (SAT)
頂點涵蓋 (Vertex Cover)

#### P=NP
意思是找答案跟證明正確一樣難。
目前人類相信 $P \neq NP$（直覺上找答案更難），但還沒有證明。

### Boyer-Moore （需建立 L(x), LastOccurrence function）
$T$ 目標字串
$P$ 匹配字串
左到右
從 (T最後一個字符) = (P最後一個字符) 比較
遇到不匹配的
Case 1 => (當前 T) 存在於 \(P 後方)
如:

  v
??xa
xcba
=>
   v
xa??
xcba

把 (當前 T) 對齊到 (P 存在當前 T) 的位置
Case 2 => (當前 T) 存在於 \(P 前方(已比較的))
如:

 v
?xax
cwax
=>
   v
xax?
cwax

P 往右一格
Case 3 => No x in P
如:

  v
??xa
dcba
=>
    v
xa???
 dbba

把 P[0] 對到 i+i (當前比較的右邊)

#### 範例

a_par **t** t **e** rn_m **a** tchi **n** g_al **g** o **rithm**
rithm

(t,m) Case 1, move to p(t)
(e,m) Case 3, move to i+1
(a,m) Case 3, move to i+1
(n,m) Case 3, move to i+1
(g,m) Case 3, move to i+1
(h,m) Case 1, move to p(m)
(m,m), (h,h), ..., (r,r) good, finished

#### L(x) (Last Occurrence Function)
P="abcabc"
A={a,b,c,d}
L(x) 是最後一次該 x 出現的位置，沒出現以 -1 代表，長度為 |A|。

### KMP 演算法(需建立 F(k), Failure function)
左字符到右字符比
複雜度 $O(|T|+|P|)$

範例:
p = abcdabc
prefix\(p) = a, ab, abc, abcd
suffix\(p) = c, bc, abc, dabc
abc 是重複出現了
想法是前綴是否出現在 p 中

lps table (Longest Proper Prefix )
abcdabeabf
0000120120
在 p 中找 p[i] = p[0] ，如果成立，找 p[i+1]=p[1]，對每個都這樣做

abcdeabfabc
00000120123

aaaabaacd
012301200
p[1] = p[0]
p[2] = p[1]
p[3] = p[2]

t = ababcabcabababd
p = ababd
lps = 00120

v
ababcabcabababd
ababd
=> 匹配直到錯
    v
ababcabcabababd
ababd
=> lps(v-1=b) => lps(b)=2 => 2 = a
    v
ababcabcabababd
  ababd
=> lps(v-1=b) => lps(b)=0 => No
     v
ababcabcabababd
     ababd
=> 匹配直到錯
       v
ababcabcabababd
     ababd
=> lps(v-1=b) => lps(b)=0 => No
        v
ababcabcabababd
        ababd
=> 匹配直到錯
            v
ababcabcabababd
        ababd
=> lps(v-1=b) => lps(b)=2 => 2 = a
            v
ababcabcabababd
          ababd
=> 匹配到結束，成功