# algo compare table

## All Sort

初階：Insertion sort、Selection sort、Bubble sort、Shell sort
高階：Quick sort、Merge sort、Heap sort
Linear Time：Radix sort、Counting sort

| Time/Space | Best | Worst | Average | Space | Stable/Unstable |
| -------- | -------- | -------- | -------- | -------- | -------- |
| Insertion sort | O(n) | O($n^2$) | O($n^2$) | O(1) | O(S) |
| Selection sort | O($n^2$) | O($n^2$) | O($n^2$) | O(1) | O(U) |
| Bubble sort | O(n) | O($n^2$) | O($n^2$) | O(1) | O(S) |
| Shell sort | O($n^\frac{3}{2}$) | O($n^2$) | O($n^2$) | O(1) | O(U) |
| Quick sort | O($nlogn$) | O($n^2$) | O($nlogn$) | O(1) | O(U) |
| Merge sort | O($nlogn$) | O($nlogn$) | O($nlogn$) | O(n) | O(S) |
| Heap sort | O($nlogn$) | O($nlogn$) | O($nlogn$) | O(1) | O(U) |
| Radix sort | O(d * (n+r)) | O(d * (n+r)) | O(d * (n+r)) | O(r * n) | O(S) |
| Counting sort | O(n+k) | O(n+k) | O(n+k) | O(n+k) | O(S) |

## Graph

Graph performance：
* Adjacency Matrix
* Adjacency Lists
* Adjacency Multilist
* Index Array
* Incidence Matrix

| | space |
| -------- | -------- |
| Adjacency Matrix | O($n^2$) |
| Adjacency Lists | O(n+e) |
| Adjacency Multilist | O(n+e) |

### Graph Traversal

| | | DFS | BFS |
| -------- | -------- | -------- | -------- |
| | 輔助的data structure | Stack | Queue |
| Time | Adjacency matrix | O($n^2$) | O($n^2$) |
| Time | Adjacency Lists | O(n+e) | O(n+e) |

### Min. Spanning Tree & Shortest Path

Min. Spanning Tree
皆採用 "Greedy" Stragety
| Kruskal's Algo | Prim's Algo | Sollin's Algo (Borůvka's) |
| -------- | -------- | -------- |
| O($ElogE$) | O($n^2$)，n=｜V｜ | worst：O((V+E)$logV$)，Avg：O(V+E) |

Shortest path
| | Length problem DAG Shortest Path Length | Dijkstra's Algo | Bellman's Algo | Hoyd-warshall Algo |
| -------- | -------- | -------- | --- | --- |
| 適用圖形 | 不具cycle的有向圖(Direct Acyclic Graph) | 有向圖，可有cycle | 同左 | 同左 |
| 可否有負邊 | Yes | No | Yes | Yes |
| 解決問題 | 單點到各點之shortest path長度 | single-source-to-other Destintions | 同左 | All pairs of vertex 之 shortest path length |
| 策略 | Topological sort | Greedy | Dynamic programming | Dynamic programming |
| Time | O(V+E) | 矩陣：O($V^2$) | O($V^3$) or O(E*V) | O($V^3$) |
| 可否有負長度cycle | No | No | No | No |

## Heap

| | Heap | Leftist Heap |
| -------- | -------- | -------- |
| Insert $X$ | O($logn$) | O($logn$) |
| Delete-min | O($logn$) | O($logn$) |
| ★Merge two Heap | O($n$) | O($logn$) |

Fibonacci Heap：
* Delete X：O($logn$)
* Decrease-key of X：O(1)

Algo版
| | Binomial Heap | Binary Heap(worst-case) | Fib. Heap(Amortized) |
| -------- | -------- | -------- | --- |
| Make-Heap(建立空Heap) | O(1) | Θ(1) | Θ(1) |
| Insert | O($logn$) | Θ($logn$) | Θ(1) |
| Minimum | O($logn$) | Θ(1) | Θ(1) |
| Extract-min | O($logn$) | Θ($logn$) | O($logn$) |
| union(Merge) | O($logn$) | Θ(n) | Θ(1) |
| Decrease-key | O($logn$) | Θ($logn$) | Θ(1) |
| Delete | O($logn$) | Θ($logn$) | O($logn$) |

＃Heap終究是Heap，不能做搜尋

## Search

#### Linear(or sequential) search
* Search前不須事先排序
* Data可保存在Random Access(e.q. Array)或Sequential Access(e.q. link list)機制皆可支持
* 適用少量Data之Search
* Time：O(n)，Explain：平均比較次數 $\frac{n+1}{2}$ 次

#### Binary Search
* 須事先排序(e.q. 小->大)
* data須保存在Random Access(e.q. Array)機制
＃Note：其他Fib Search，interpolation Search也是
* Binary Search Algo：
* Iterative
* Recursive

* n筆Data
1. 以Binary Search Tree作Search for X則
**Worst case Time：O(n)**，**Best case Time：O($logn$)**
2. 以Binary Search Tree作Search for X則
**Worst case Time：O($logn$) (Avg/Best)**

## Balanced Tree

#### AVL Tree
| AVL Tree | 高度平衡化(最小化)：worst case | Dynamic Data情況下，BST可能形成skewed structure：worst case |
| -------- | -------- | -------- |
| Search/Insert/Delete | O($logn$) | O(n) |

#### AVL Tree、Link list、Array
| operations | Array | Link list | AVL Tree |
| -------- | -------- | -------- | --- |
| Search for X | O($logn$) | O(n) | O($logn$) |
| Search for $k$th item | O(1) | O($k$) | O($logn$) |
| Delete X | O(n) | O(1) | O($logn$) |
| Delete $k$th item | O(n-k) | O($k$) | O($logn$) |
| Insert X | O(n) | O(1) | O($logn$) |
| Output in order | O(n) | O(n) | O(n) |

## OS
https://zys-notes.blogspot.com/2020/10/blog-post_15.html
### CPU Scheduing algo
* CPU↑ 利用率
* Throughput↑ 產能
* Waiting Time↓ 等待時間
* Turnaround Time↓ 完成時間
* Response Time↓ 回應時間

#### Scheduing algo
* FCFS(不插隊)：最差，先到先做
* SJF(不插隊)：排班效益是Optimal，Avg.w.t最小，較不適用在Short-term scheduler
* SRTF(插隊)：相較SJF平均w.t.更小，但會付出較多Context Switching負擔
* Priority(最大優先)：最大尾的優先，若權利相同則FCFS，可參數化法則，優先權高低定義可以衍生不同排班行為
* RR：效能取決於Time Quantum大小制定，常用於Time-Sharing Sys