Độ phức tạp thuật toán & Big-O
Ngôn ngữ chung để so sánh thuật toán: Big-O/Omega/Theta, phân tích time/space complexity, và vì sao "chạy được" khác "chạy tốt ở quy mô lớn".
Không có ngôn ngữ chung để nói về hiệu năng, mọi cuộc thảo luận về "thuật toán nào tốt hơn" chỉ là cảm tính. Big-O là công cụ định lượng cho phép so sánh khách quan — và là kỹ năng nền tảng bắt buộc trước khi học bất kỳ thuật toán/cấu trúc dữ liệu cụ thể nào trong các module tiếp theo.
🎯 Mục tiêu học tập
- Phân tích được time complexity và space complexity của 1 đoạn code bất kỳ
- Phân biệt Big-O (worst case), Big-Omega (best case), và Big-Theta (tight bound)
- Nhận diện các lớp độ phức tạp phổ biến và cảm nhận trực quan sự khác biệt ở quy mô lớn
- Áp dụng tư duy độ phức tạp để đánh giá nhanh 1 giải pháp trước khi viết code chi tiết
Big-O — ngôn ngữ chung để so sánh thuật toán
Big-O mô tả tốc độ tăng của thời gian chạy (hoặc bộ nhớ dùng) khi kích thước đầu vào (n) tăng lên, bỏ qua hằng số và các số hạng bậc thấp — vì ở n đủ lớn, số hạng bậc cao nhất luôn chi phối. O(n) nghĩa là "thời gian chạy tăng tuyến tính theo n", không quan tâm hệ số 2n hay 5n vì cùng thuộc lớp O(n).
| Ký hiệu | Ý nghĩa |
|---|---|
| Big-O — O(f(n)) | Giới hạn trên (worst case) — "không bao giờ chậm hơn mức này" |
| Big-Omega — Ω(f(n)) | Giới hạn dưới (best case) — "không bao giờ nhanh hơn mức này" |
| Big-Theta — Θ(f(n)) | Giới hạn chặt (khi Big-O và Big-Omega trùng nhau) — mô tả chính xác nhất |
Trong thực hành hàng ngày, kỹ sư hầu như chỉ nói về Big-O (trường hợp xấu nhất) vì đó là cam kết an toàn nhất — hệ thống production cần biết "chậm nhất là bao nhiêu", không chỉ "nhanh nhất có thể".
Các lớp độ phức tạp phổ biến — cảm nhận trực quan
| Độ phức tạp | Tên gọi | Ví dụ | n = 1.000.000 mất khoảng |
|---|---|---|---|
| O(1) | Hằng số | Truy cập phần tử mảng theo index | Tức thì |
| O(log n) | Logarit | Tìm kiếm nhị phân, thao tác trên cây cân bằng | ~20 bước |
| O(n) | Tuyến tính | Duyệt qua mảng 1 lần | 1 triệu bước |
| O(n log n) | Tuyến tính-logarit | Sắp xếp hiệu quả (Merge Sort, Quick Sort trung bình) | ~20 triệu bước |
| O(n²) | Bậc hai | Vòng lặp lồng nhau, sắp xếp nổi bọt | 1.000 tỷ bước — không khả thi |
| O(2ⁿ) | Mũ | Đệ quy brute-force không tối ưu (ví dụ Fibonacci ngây thơ) | Không thể tính xong trong đời người |
Với n nhỏ (vài chục phần tử), thuật toán O(n²) có thể nhanh hơn O(n log n) vì hằng số ẩn (constant factor) — Big-O chỉ có ý nghĩa quyết định khi n đủ lớn. Đừng tối ưu Big-O cho dữ liệu chắc chắn luôn nhỏ; nhưng luôn cảnh giác khi dữ liệu có khả năng tăng trưởng không giới hạn theo thời gian (đúng tinh thần Scalability đã học ở khoá Architecture, Module 7).
Phân tích Time & Space Complexity của Code thật
def tim_phan_tu_trung_lap(arr): # arr có n phần tử
seen = set() # O(n) space cho set
for x in arr: # vòng lặp chạy n lần -> O(n) time
if x in seen: # tra cứu trong set: O(1) trung bình
return x
seen.add(x) # thêm vào set: O(1) trung bình
return None
# Tổng: Time O(n), Space O(n)
def tim_phan_tu_trung_lap_cham(arr): # cách tiếp cận "ngây thơ"
for i in range(len(arr)):
for j in range(i + 1, len(arr)): # vòng lặp lồng nhau
if arr[i] == arr[j]:
return arr[i]
return None
# Tổng: Time O(n²), Space O(1) — nhanh hơn về bộ nhớ nhưng chậm hơn nhiều về thời gian với n lớn
Đây chính là đánh đổi Time vs Space — chủ đề trung tâm sẽ lặp lại xuyên suốt cả khoá học: cách đầu dùng thêm bộ nhớ (hash set) để đổi lấy tốc độ nhanh hơn nhiều, cách sau tiết kiệm bộ nhớ nhưng chậm hơn hẳn ở quy mô lớn — không có câu trả lời "đúng tuyệt đối", chỉ có đánh đổi phù hợp với ràng buộc cụ thể (đúng tư duy trade-off đã học ở khoá Architecture, Module 1).
🏋️ Bài tập thực hành
Lấy 3 đoạn code bạn đã viết ở các khoá học trước (ví dụ hàm xử lý dữ liệu ở khoá AI Engineer, hoặc 1 endpoint Laravel). Với mỗi đoạn, viết ra Big-O cho cả time và space complexity, giải thích rõ dòng nào đóng góp vào độ phức tạp đó. Nếu tìm thấy đoạn nào có độ phức tạp cao hơn cần thiết (ví dụ O(n²) khi có thể làm O(n log n)), ghi chú lại hướng cải thiện.
📚 Tài nguyên học tập
-
Big-O Cheat SheetBảng tra cứu nhanh độ phức tạp của các cấu trúc dữ liệu/thuật toán phổ biếnReference
-
MIT OCW — Introduction to AlgorithmsKhoá học thuật toán nền tảng của MIT, miễn phíKhoá học
✅ Tự đánh giá hoàn thành
- Phân tích đúng Big-O cho time và space complexity của 1 đoạn code bất kỳ
- Phân biệt được Big-O, Big-Omega, Big-Theta
- Nhận diện nhanh 6 lớp độ phức tạp phổ biến và cảm nhận được sự khác biệt ở quy mô lớn
- Áp dụng được tư duy đánh đổi Time vs Space cho 1 tình huống thực tế