"We need to solve large problems with constant-sized code, correctly and efficiently.” (→ Chúng ta phải giải quyết bài toán lớn bằng mã ngắn gọn, chính xác và hiệu quả.)
| Concept | Meaning | Example / Note |
|---|---|---|
| Asymptotics | Phân tích tốc độ tăng trưởng của hàm thời gian (Time Complexity). | O(n), O(log n), O(n log n)... |
| Recurrence Relations | Công thức mô tả lời giải đệ quy. | T(n) = 2T(n/2) + n |
| Solving Recurrences | Dùng: Substitution, Recursion Tree, Master Theorem. | Giải độ phức tạp merge sort |
| Model of Computation | Giả định về máy tính (RAM model). | Word-RAM: thao tác cơ bản O(1). |
| Step | Strategy | Example |
|---|---|---|
| 1 | Reduce to a known problem | Chuyển sang sắp xếp, tìm kiếm, shortest path... |
| 2 | Use a known algorithm | Sort → MergeSort, QuickSort; Search → BinarySearch |
| 3 | Use a known data structure | Queue, Heap, HashMap, Tree, Graph |
| 4 | Design recursively | Brute Force → Divide & Conquer → DP → Greedy |
| Algorithm | Time | In-place? | Stable? | Notes |
|---|---|---|---|---|
| Insertion Sort | O(n²) | ✅ Yes | ✅ Yes | Tốt cho dữ liệu gần sắp xếp |
| Selection Sort | O(n²) | ✅ Yes | ❌ No | Ít swap |
| Merge Sort | O(n log n) | ❌ No | ✅ Yes | Tối ưu so sánh |
| Heap Sort | O(n log n) | ✅ Yes | ❌ No | Dùng heap; tiết kiệm bộ nhớ |
| Counting Sort | O(n + u) | ❌ No | ✅ Yes | Dữ liệu nguyên nhỏ |
| Radix Sort | O(n log u) | ❌ No | ✅ Yes | Dữ liệu có giới hạn chữ số |
“Don’t just code. Think algorithmically.”
| Type | Internals? | Externals? | Description |
|---|---|---|---|
| Mechanical | ✅ | ❌ | Hiểu rõ cách DS hoạt động (linked list, heapify...) |
| Reduction | ❌ | ✅ | Biết áp dụng giải pháp sẵn có (sort, search...) |
| Modification | ✅ | ✅ | Biết biến đổi hoặc mở rộng thuật toán (augment tree, divide-conquer...) |