Cheat sheet
ทุกสูตรและตัวเลขที่ต้องจำในวิชานี้ รวมไว้หน้าเดียว
ลำดับอัตราการโต
O(1) << O(log n) << O(n) << O(n log n) << O(n²) << O(2ⁿ)
ดีสุด <---------------------------------------> แย่สุด
วิธีเทียบ 2 ฟังก์ชัน:
lim (n→∞) f(n)/g(n) = ∞ → f โตเร็วกว่า
= 0 → g โตเร็วกว่า
= C → โตเท่ากัน
Big-O และเพื่อน ๆ
| สัญลักษณ์ | ความหมาย | ใช้กับ |
|---|
| O(f) | ≤ f | worst case / ขอบบน |
| Ω(f) | ≥ f | best case / ขอบล่าง |
| Θ(f) | = f | best = worst |
| o(f) | < f | ขอบบนแบบเข้ม |
| ω(f) | > f | ขอบล่างแบบเข้ม |
O(n+1) = O(n) O(n+c) = O(n) O((n²-n)/2) = O(n²)
Searching
| อัลกอริทึม | Best | Worst | เงื่อนไข |
|---|
| Linear Search (มี return) | Ω(1) | O(n) | ข้อมูลไม่ต้องเรียง |
| Linear Search (ไม่มี return) | Θ(n) | วนครบทุกกรณี |
| Binary Search | Ω(1) | O(log n) | ข้อมูลต้องเรียงแล้ว |
Sorting
| อัลกอริทึม | Best | Worst | หน่วยความจำเพิ่ม | จุดสังเกต |
|---|
| Bubble (ไม่มี flag) | Θ(n²) | Θ(n²) | ไม่มี | j < n-i-1 |
| Bubble (มี flag swapped) | Ω(n) | O(n²) | ไม่มี | break เมื่อไม่มี swap |
| Insertion | Ω(n) | O(n²) | ไม่มี | เหมือนจัดไพ่ในมือ |
| Merge | Θ(n log n) | Θ(n log n) | ต้องใช้ array ชั่วคราว | divide and conquer |
| Tower of Hanoi | O(2ⁿ) | — | recursion 2 สาย |
โครงสร้างข้อมูล — เวลาค้นหา
| โครงสร้าง | Search |
|---|
| Array | O(n) |
| Sorted Array | O(log n) |
| Stack / Queue / Linked list | O(n) |
| Binary Search Tree (balanced) | O(log n) |
| Binary Search Tree (เอียงสุด) | O(n) |
| Hash Table (กระจายดี) | Θ(1) |
| Hash Table (ชนกันหมด) | O(n) |
สูตรของ Tree
Depth ของ node = ความยาวเส้นทางขึ้นไปถึง root (มองขึ้น)
Height ของ node = ความยาวเส้นทางที่ยาวสุดลงถึง leaf (มองลง)
Height ของ tree = height ของ root
Complete binary tree height k → node มากสุด = 2^(k+1) - 1
BST: log₂n ≤ h ≤ n และเวลาค้นหา = O(h)
| ชนิด binary tree | เงื่อนไข |
|---|
| Full | ทุก node มีลูก 0 หรือ 2 ตัว |
| Complete | เต็มทุกชั้นยกเว้นชั้นล่างสุดที่เรียงชิดซ้าย |
| Perfect | เต็มทุกชั้น leaf อยู่ชั้นเดียวกันหมด |
| Balanced (AVL) | height ซ้าย–ขวาต่างกันไม่เกิน 1 ทุก node |
Traversal
| แบบ | ลำดับ | โครงสร้างที่ใช้ | หมายเหตุ |
|---|
| Preorder | Root, Left, Right | stack / recursion | — |
| Inorder | Left, Root, Right | stack / recursion | BST ได้ค่าเรียงน้อยไปมาก |
| Postorder | Left, Right, Root | stack / recursion | — |
| BFS (level order) | ทีละชั้น ซ้ายไปขวา | queue | การันตีเส้นทางสั้นสุด |
ต้นไม้ตัวอย่างในบทเรียนให้ผลดังนี้:
Preorder : 1, 8, 3, 4, 9, 5, 6, 2, 0, 7
Inorder : 3, 8, 9, 4, 5, 1, 2, 0, 6, 7
Postorder : 3, 9, 5, 4, 8, 0, 2, 7, 6, 1
BFS : 1, 8, 6, 3, 4, 2, 7, 9, 5, 0
สูตรของ Graph
Complete directed graph E = N(N-1)
Complete undirected graph E = N(N-1)/2
Tree E = V - 1
MST ของกราฟ V vertex E = V - 1
ความยาว path ที่มี n vertex = n - 1
| คำถาม | Matrix | List |
|---|
| u,v ติดกันไหม | Θ(1) | O(V) |
| เพื่อนบ้านของ v มีใครบ้าง | O(V) | Θ(จำนวนเพื่อนบ้าน) |
| หน่วยความจำ | V² | V + E |
| อัลกอริทึม | แก้ปัญหาอะไร | แนวคิด |
|---|
| Prim | MST | greedy ขยายจาก vertex เดียว |
| Kruskal | MST | greedy เรียง edge ทั้งกราฟ ข้ามเส้นที่ทำให้เกิด cycle |
| Dijkstra | shortest path จาก source | relaxation: d(u)+w < d(v) แล้วอัปเดต |
| BFS | shortest path ในกราฟไม่ถ่วงน้ำหนัก | queue ไล่ทีละชั้น |
Hash Table
Division method hash(key) = key % m
Multiplication method hash(key) = m × ( key×A - ⌊key×A⌋ ), 0 < A < 1
Uniform hash(key) = key × (m / X)
Load factor ∝ = n / m
| วิธีแก้ collision | กลุ่ม | ลำดับการ probe |
|---|
| Separate Chaining | close addressing | ต่อ linked list ในช่องเดิม |
| Linear Probing | open addressing | hash+1, hash+2, hash+3, … |
| Quadratic Probing | open addressing | hash+1, hash+4, hash+9, … (hash+k²) |
| Double Hashing | open addressing | hash + k×hash2(key) |
Recurrence ที่ต้องจำ
| สมการ | ผลลัพธ์ | มาจาก |
|---|
| T(n) = T(n/2) + c | O(log n) | Binary search |
| T(n) = 2T(n/2) + k | O(n) | Divide step ของ merge sort |
| T(n) = 2T(n/2) + n | Θ(n log n) | Merge sort เต็มรูปแบบ |
| T(n) = 2T(n-1) + 1 | O(2ⁿ) | Tower of Hanoi |
กับดักข้อสอบ
- Binary search ต้องใช้ข้อมูลที่เรียงแล้ว — ถ้าโจทย์ให้ array มั่ว ๆ ใช้ไม่ได้
- Bubble sort ที่ไม่มี flag เป็น Θ(n²) ไม่ใช่ Ω(n) — best case ดีขึ้นได้ต่อเมื่อใส่ flag
- Merge sort ไม่มี best case ที่ดีกว่า — Θ(n log n) ทุกกรณี
- BST ที่ใส่ข้อมูลเรียงมาแล้ว จะกลายเป็นเส้นตรง ค้นหา O(n)
- เงื่อนไข BST ต้องจริงกับทุก node ใน subtree ไม่ใช่แค่ลูกที่ติดกัน
- ลบใน linear probing ห้ามปล่อยช่องว่างเปล่า ต้องทำเครื่องหมาย deleted
- MST ไม่เท่ากับ shortest path tree — คนละปัญหา
- BFS การันตีเส้นทางสั้นสุด DFS ไม่การันตี
- COUNT ที่ใช้กับ LEFT JOIN ในบทฐานข้อมูลก็คนละเรื่องกับที่นี่ — อย่าสับสนสองวิชา