---
robots: index, follow
tags: NCTU, CS, 共筆, 演算法概論, 吳育松
description: 交大資工課程學習筆記
lang: zh-tw
dir: ltr
breaks: true
disqus: calee
GA: UA-100433652-1
---
演算法概論--吳育松
=====
`NCTU` `CS`
[回主頁](https://hackmd.io/s/ByOm-sFue)

# Syllabus
- Grade

# Course
## Ch1 Introduction
What is algorithm
- ex: `How to find the k'th big number in a sequence`
- just compare
- sort
- quick sort like
- Need
- correct
- time efficiency
- $O(f(n))$
$O(g(x))=f(x)$ if $\forall{x}>x_1\Rightarrow f(x)<c\cdot g(x)$
- $\Theta(f(n))$
$\Theta(g(x))=f(x)$ if $O(g(x)=\Omega(x)=f(x)$
- $\Omega(f(n))$
$\Omega(g(x))=f(x)$ if $\forall{x}>x_1\Rightarrow f(x)>c\cdot g(x)$
- 不要理常數
- space efficiency
- 每個操作會因硬體上的差距而有所不同 (ex. 記憶體離 CPU 的距離)
- readable (easy to maintain)
- Tools required to answer
- execution model: RAM (random ascess machine)
- Math tool
- discrete combinatorics
- elementary probability
- algebraic dexterity
- methods of identifying most significant terms
- Asymptotic Analysis (漸進分析)
order of growth
- SORT
- insertion sort
- incremental approach
- incremental
一次只做一件事情 [參考](http://www.csie.ntnu.edu.tw/~u91029/AlgorithmDesign.html)
- merge sort
- Divide-and-Conquer Algorithms
- divide
- conquer
- combine: 最難的
- $T(n) = \begin{cases}
\theta(1) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n = 1 \\
2T(\frac n 2)+\theta(n)\ \ \ n>1
\end{cases}$
- $Θ(n\lg n)$

## CH2 Asymptotics and Mathematical Basics
Complexicity
### $\Theta(n)$
$$
Θ(g(n)) = {\{f(n)| ∃c_1, c_2, n_0 >0 \ s.t.\\
\ 0 ≤ c\ 1g(n) ≤ f(n) ≤ c_2\ g(n), ∀n ≥ n_0\}}
$$
or $\Theta(g(x))=f(x)$ if $O(g(x)=\Omega(x)=f(x)$
:::info
e.g. prove $6n^3 \not= Θ(n^2)$
assume $6n^3 = Θ(n^2)$
$0 ≤ c_1n^2 ≤ 6n^3 ≤ c_2n^2, ∀n ≥ n_0$
$0 ≤ c_1 ≤ 6n ≤ c_2, ∀n ≥ n_0$
This implies that $n ≤ \frac{c_2}{6}$ , $∀n ≥ n_0$, a contradiction.
:::
- When $\Theta$ appears in a formula, we interpret it as standing for some anonymous function that shall remain nameless.
- e.g. $2n^2 + 3n + 1 = 2n^2 + Θ(n)$ means: $2n^2 + 3n + 1 = 2n^2 + f(n)$, where f (n) is some function in the set Θ(n)
- 可以簡化多餘的項

### $O(n)$ (upper bound)
$$
O(g(n)) = {\{f(n)| ∃ c, n_0\ > 0 \ s.t. \\
0 ≤ f (n) ≤ cg(n), ∀n ≥ n_0 \}}
$$
- e.g. $5n^2 + 100n + 22 = O(n^2) = O(n^3)$

### $\Omega(n)$ (lower bound)
$$
Ω(g(n)) = {\{f(n)| ∃ c, n_0 > 0 \ s.t. \\
0 ≤ cg(n) ≤ f(n), ∀n ≥ n_0 \}}
$$
- e.g. $5n^2 + 100n + 22 = Ω(n^2) = Ω(n)$

### $o(n)$ (upper bound, not asymptotically tight)
$$
o(g(n)) = {\{f(n)| ∀ c > 0, ∃ n_0 > 0\ s.t. \\
0 ≤ f(n) < cg(n), ∀n ≥ n 0 \}}
$$
- 上限，但是因為對所有 c，所以是"不會碰到"的上限
- $f(n) = o(g(n)) → \underset{n→∞}\lim(\frac{f(n)}{g(n)})=0$
- e.g. $2n = o(n^2)$
- e.g. $2n^2 \not= o(n^2)$

### $\omega(n)$ (lower bound, not asymptotically tight)
$$
ω(g(n)) = {\{f(n)| ∀ c > 0, ∃ n_0 > 0 \ s.t.\\
0 ≤ cg(n) < f (n), ∀n ≥ n_0 \}}
$$
- "不碰到的"下限
- $f(n) = o(g(n)) → \underset{n→∞}\lim(\frac{f(n)}{g(n)})=∞$
- e.g. $\frac{n^2}{2} = ω(n)$
- e.g. $\frac{n}{2} \not= ω(n)$

### 性質
- Transitivity (遞移律)
$f(n)=X(g(n)), g(n)=X(h(n))\to f(n)=X(h(n))$, X = all notation
- Reflexivity (反射性)
$f (n) = Θ(f (n))$
$f (n) = O(f (n))$
$f (n) = Ω(f (n))$
- Symmetry (對稱性)
$f (n) = Θ(g(n)) \iff g(n) = Θ(f (n))$
- Transpose Symmetry (轉置對稱)
$f (n) = O(g(n)) \iff g(n) = Ω(f (n))$
$f (n) = o(g(n)) \iff g(n) = ω(f (n))$

### 證明方法
- 定義
- 反證
- $\underset{n→∞}\lim\frac{f(n)}{g(n)}=c, c\not=0 \to f(n) = Θ(g(n))$
- L’Hôpital’s Rule (羅畢達)

### 常見複雜度公式：
- Polynomials (多項式): $p(n)=O(n^k)$ (k是最高次)
- Exponentials (指數): $e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+...+\frac{x^n}{n!}=\sum_{i=0}^{100}\frac{x^i}{i!}$
- logarithm
- binary logarithm: $\lg n = \log_2 n$
- natural logarithm: $\ln n = \log_e n$
- exponentiation: $\lg^k n = (\lg n)^k$
- composition: $\lg \lg n = \lg(\lg n)$
- Rates of Growth: $O(e^x) > O(p(x))$
- OwO: $lg(n!) = O(nlgn)$
:::info
Stirling’s Approximation
$$
n! = \sqrt{2\pi n}(\dfrac ne)^n(1 + \Theta(\dfrac 1 n))
$$
:::
- [$lg(n!)$的另一種證明](http://stackoverflow.com/questions/2095395/is-logn-%CE%98n-logn)
- 費氏數列
$0, 1, 1, 2, 3, 5, 8, ...$
golden ratio $\phi$
### Useful Identities
- $2^{\lg n}=n^{\lg 2}=n$
- $4^{\lg n}=n^{\lg 4}=n^2$
- $(\lg n)^{\lg n} = n^{\lg\lg n}$
- $2=n^{\frac{1}{\lg n}}$
- $(\sqrt{2})^{\lg n}=2^{\frac1 2\lg n}=2^{\lg{\sqrt2}}=\sqrt{n}$
- $n!=\sqrt{2\pi n}(\frac e n)^n(1+\Theta(\frac1 n))$
- $n!=\Theta(n^{n+\frac1 2}e^{-n})$
- $(\lg n)!=\Theta((\lg n)^{n+\frac1 2}e^{-n})=\Theta((\lg n)^{n+\frac1 2}n^{-\lg e})$
- $lg(n!) = Θ(n\lg n)$
- $n! = o(n^n)$
- $n! = ω(2^n)$

## Ch3
級數求和(跳過O_O)

## Ch4 Recurrences
### 3 method
- Substitution Method:
**Guess** the bound and prove by induction
e.g. using divide and conquer
$T(n) = 2T(\dfrac n 2) + 2$

- Iteration Method:
Treat it as summation
e.g using infinite geometric series

- Master Method:
$T(n) = aT(\dfrac n b) + f(n)$, $a \ge 1$, $b > 1$
**Case 1:** If $f(n) = O(n^{\log _ba-\epsilon })$ for some constant $\epsilon > 0$, then $T(n) = \Theta(n^{\log _ba})$.

**Case 2:** If $f(n) = \Theta (n^{\log _ba})$ then $T(n) = \Theta (n^{\log _ba} \lg n)$.

**Case 3:** If $af(\frac {n}{b}) \leq cf(n)$ for some constant $c < 1$ and $n \geq b$, then $T(n) = \Theta(f(n))$.

### e.g.
1.Divide and Conquer
- Merge-Sort
$$T(n) = 2T(\dfrac n 2) + \Theta(n)$$
=> $\Theta(n\lg n)$
- MAX-MIN
$$T(n) = 2 + 2T(\dfrac n 2)$$
=> $\Theta(n)$

## Ch5 Heap Sort
Sorting
- Kind
- Insertion Sort: $\theta(n^2)$
- Merge Sort: $\theta(nlogn)$
- Heap Sort: $\theta(nlogn)$
- Quick Sort: $\theta(nlogn)$, $O(n^2)$
- Way
- Comparison Sort
- In-place Sort
- Stable Sort

- Heap Sort
- $HEAPIFY(A, i)$
1.$\space\space$$l \leftarrow LEFT(i)$
2.$\space\space$$r \leftarrow RIGHT(i)$
3.$\space\space$**if** $l \leq heap-size[A]$ and $A[l] > A[i]$
4.$\space\space$$\space\space\space\space$**then** $largest \leftarrow l$
5.$\space\space$$\space\space\space\space$**else** $largest \leftarrow i$
6.$\space\space$**if** $r \leq heap-size[A]$ and $A[r] > A[largest]$
7.$\space\space$$\space\space\space\space$**then** $largest \leftarrow r$
8.$\space\space$**if** $largest \neq i$
9.$\space\space$$\space\space\space\space$**then** exchange $A[i] \leftrightarrow A[j]$
10.$\space\space\space\space$$\space\space\space\space\space\space\space\space$$HEAPIFY(A, largest)$

- $BUILD-HEAP(A)$
1.$\space\space heap-size[A] \leftarrow length[A]$
2.$\space\space$**for** $i \leftarrow \lfloor\frac{length[A]}{2}\rfloor$ **downto** 1
3.$\space\space\space\space\space\space$**do** $HEAPIFY(A,i)$

- $HEAPSORT(A)$
1.$\space\space BUILD-HEAP(A)$
2.$\space\space$**for** $i \leftarrow length[A]$ **downto** 2
3.$\space\space\space\space\space\space\space\space$**do** exchange $A[1] \leftrightarrow A[i]$
4.$\space\space\space\space\space\space\space\space\space\space\space\space\space heap-size[A] = heap-size[A] - 1$
5.$\space\space\space\space\space\space\space\space\space\space\space\space\space HEAPIFY(A,1)$
## Ch6 Quick Sort
## Ch8 i'th order
### SELECT
- brute-force
- need to sort first
- sorting $O(n\lg(n))$ (maybe, depand on which sort you used)
- search $O(1)$
- qSort approach
- don't need to sort
- 類似 binary search
- 檢查pivot
- 若非,把比pivot小的放左邊,反之放右邊
- 去要找的group遞迴
- $O(n^2)$
- $\theta(n\lg(n))$
- Worst Case Linear Time

## Set
key -> data
Search
Insert
Delete
Minimum
- hash table
- if same slot
1. chaining
link list
2. open addressing

# HW
[codesensor](https://codesensor.tw/)
//這個網站超難用的QQ
- HW1
- 純sort水題
- 優化 IO
- HW2
- 也是sort
- 用msgpack包裹
- HW3
- suffix tree
- SAM -> O_O
- [問題討論區](https://hackmd.io/CwDgpgjAxmCcBGBaeAmMTgQIYsSKKAJolgGYBsAzIefFPJQOyFA=)
- 參考：
- [台大資工演算法投影片](http://www.csie.ntu.edu.tw/~hil/algo2011spring/algo2011spring09.pptx)
- http://www.geeksforgeeks.org/ukkonens-suffix-tree-construction-part-2/
- http://hlfu.math.nctu.edu.tw/getCourseFile.php?CID=147&type=browser
- [SAM 參考](http://codingsimplifylife.blogspot.tw/2016/02/sam.html)
- HW4
- [問題討論區](https://hackmd.io/CbDGDNgBgJgQwLQHYqiQgLADlFBdQBGDBANgFMoBOLKQ8gIzgdCA)
- 背包問題
- 兩個背包
# Exam
> 廢話區
> >QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
>
> >加油！！！！！！！！！！！[name= Marco Liu]