Algorithms & Applications
Trang chủ / Module 1
📐 Module 1 / 14 · 4-5 ngày

Độ 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".

Big-OPhân tích
📌 Vì sao module này quan trọng

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ạpTên gọiVí dụn = 1.000.000 mất khoảng
O(1)Hằng sốTruy cập phần tử mảng theo indexTức thì
O(log n)LogaritTì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ínhDuyệt qua mảng 1 lần1 triệu bước
O(n log n)Tuyến tính-logaritSắp xếp hiệu quả (Merge Sort, Quick Sort trung bình)~20 triệu bước
O(n²)Bậc haiVòng lặp lồng nhau, sắp xếp nổi bọt1.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
⚠️ Bài học thực tế

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

Phân tích độ phức tạp của code thật

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

✅ 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ế