1. Độ phức tạp Big-O
| Ký hiệu | Tên | Ví dụ |
|---|---|---|
| O(1) | Hằng số | Truy cập phần tử mảng theo chỉ số |
| O(log n) | Logarit | Tìm kiếm nhị phân |
| O(n) | Tuyến tính | Duyệt mảng |
| O(n log n) | Tuyến tính-log | MergeSort, QuickSort |
| O(n²) | Bậc hai | BubbleSort, InsertionSort |
| O(2ⁿ) | Mũ | Bài toán đệ quy Fibonacci đơn giản |
2. Mảng và Danh Sách Liên Kết
Mảng
Truy cập O(1), chèn/xóa O(n). Bộ nhớ liên tục.
Danh sách liên kết
Truy cập O(n), chèn/xóa O(1) nếu có con trỏ. Linh hoạt về kích thước.
struct Node { int data; Node* next; };
3. Stack và Queue
Stack — LIFO (Last In First Out): push, pop, top — O(1). Ứng dụng: undo/redo, kiểm tra dấu ngoặc cân bằng, DFS.
Queue — FIFO (First In First Out): enqueue, dequeue, front — O(1). Ứng dụng: hàng đợi xử lý, BFS, scheduler.
4. Cây và Đồ Thị
Cây nhị phân tìm kiếm
BST: trái < nút < phải. Tìm/chèn/xóa O(log n) khi cân bằng.
Đồ thị
Đỉnh + cạnh. Biểu diễn: ma trận kề (O(V²) bộ nhớ) hoặc danh sách kề (O(V+E)).
BFS
Dùng Queue. Tìm đường ngắn nhất khi đồ thị không trọng số.
DFS
Dùng Stack/đệ quy. Phát hiện chu trình, sắp xếp topo.
5. Bài tập lập trình
- Cài đặt Stack bằng mảng cố định 1000 phần tử. Viết hàm isBalanced(s) kiểm tra dấu ngoặc cân bằng.
- Cài đặt Queue bằng hai Stack.
- Cho mảng n số nguyên, tìm phần tử lớn thứ k bằng cách dùng Min-Heap kích thước k.
- Cài đặt BST hỗ trợ insert, find, delete. Phân tích độ phức tạp.
- Cho đồ thị có trọng số với n đỉnh, m cạnh. Cài đặt Dijkstra tìm đường ngắn nhất từ đỉnh 1 đến tất cả đỉnh còn lại (O(m log n)).