# Algorithm notes
###### tags: `Algorithm` `Datastruction` `CS`
**相較於食譜，演算法較為嚴謹，所有步驟都用數學式表達**

Big O表示「在最糟情況下的執行時間」
>使用「步驟次數」來表示執行單位

# Data Structure
**在DS下功夫，就能提高記憶體的使用效率**

## list&array
| / / / | 存取 | 追加 | 刪除 |
| 列表 | 慢 | 快 | 快 |
| 陣列 | 快 | 慢 | 慢 |
可以看出不同資料結構有不同優缺點，要先考慮哪種操作比較頻繁決定

## stack
* LIFO：隨時都只存取最新數據
* c++的cout就是stack的形式
* 深度優先搜尋，選擇最晚被加入的做頂點。
* infix to postfix（中序式轉後序式）

## queue
* FIFO：從舊有數據開始依序處理
* 廣度優先搜尋，選擇最早被加入的做頂點。
* 買票

## hash table
* key(識別符號)and value（數據內容）
* collision時，使用chaining(list)，open addressing
* 常用於關聯陣列

## heap
* 堆積最上方永遠是最小(大)的數據
* 需要頻繁地從管理數據中取出最小值
* 重整結構時，必須將最尾端數據提到最上面

## binary search tree
* 往左沿著樹狀結構最左節點，即為「最小節點」
* 往右沿著樹狀結構最右節點，即為「最大節點」
* 刪除該節點時，移動「左邊樹狀結構最大節點」or「右邊樹狀結構最小節點」皆可
* 當樹狀結構靠攏，結構將變得很高，差不多就是線性搜尋O(n)

# 五大常用演算法策略
### Greed algorithm
在每步採用**當前看起來最好的選擇**，希望使最終答案最好的方法。

### Divide and conquer
分割成一些規模較小的相同問題，以便各個擊破。
ex.quick sort. merge sort. binary search

### Backtracking(DFS)
在每階段將所有可能性列出，排除不可能的解後，往下一個階段，如所有分支均不成立，則回覆到上一個階段的搜尋。

### Branch and bound method(BFS)
類似Backtracking 但以廣度優先
### Dynamic programming
根據子問題的解以得出原問題的解
記憶化儲存，以便下次需要同一子問題解時直接查表