動態規劃 Dynamic programming

• using ‘Cache’ Memoization

動態規劃的基本思想是將「原始問題」分解成多個「子問題」，先求解並「儲存」這些子問題的解到 cache，然後通過這些子問題的解來提供給原問題。這樣做的目的是避免重複計算，從而提高算法的效率。

• Dynamic Programming = Divide-and-Conquer + Memoization (Cache)
  與 分而治之 Divide-and-Conquer 很像，但最大的差別是子問題大多類似，並先儲存子問題的解到 cache，之後需要使用到時就不用重複計算

Searching / Traversal

Search
簡易搜尋/線性搜索 Sequential Search/Linear Search - O(n)
二分搜尋 Binary Search - O(log n)

Traversal
Depth First Search (DFS) 先 上到下 再 左到右 - O(n)
Breadth First Search (BFS) 先 左到右 再 上到下 - O(n)

• DFS use lower memories than BFS

Sorting 排序

• 排序 Sorting:
  Comparison Sort

1. 氣泡排序 Bubble Sort - Time O(n) or O(n^2) / Space - O(1)

2. 選擇排序 Selection Sort - Time O(n^2) / Space - O(1)

3. 插入排序 Insertion Sort - Time O(n) or O(n^2) / Space - O(1)

4. 合併排序 Merge Sort - Time O(n log n) / Space - O(n)

5. 快速排序 Quick Sort - Time O(n log n) / Space - O(log n)

• 合併排序 Merge Sort 和 快速排序 Quick Sort 用 Divide and Conquer Recursion 方式

• Heap Sort

Non-Comparison Sort

• Counting Sort
• Radix Sort

Recursion 遞迴

• 在函式之中呼叫函式自己本身

Graph

Tree

Queue

Stack

Linked-list 鏈結串列

鏈結串列是一種常見的基礎資料結構，是一種線性序列，但是並不會按線性的順序儲存資料，而是在每一個節點裡存到下一個節點的指標。
生活例子類似火車，節點Node，像是車廂

由於不必須按順序儲存，鏈結串列在插入的時候可以達到O(1)的複雜度，但是尋找一個節點或者存取特定編號的節點則需要O(n)的時間

Operations on Linked-list

1. Insert - O(n) Append - O(1) Prepend - O(1)
2. Access Lookup- O(n)
3. Search -
4. Delete - O(n)

Map

The Map object holds key-value pairs and remembers the original insertion order of the keys.

• MDN MAP

• elements in an array do not repeat -> use Set

• elements in an object do not repeat -> use Map
  both have size, has(), and keys().

• 與Object有點類似，但Map裡面的key是唯一的，重複set會覆蓋舊的value

• Map的key除了原始型別外，可以是任何值object或function