Chuyển tới nội dung chính

Các lớp phức tạp thường gặp

Bạn sẽ học được gì

Ở bài Big-O bạn đã biết cách rút gọn. Bài này đi sâu từng lớp thường gặp: mỗi lớp trông như thế nào trong code, ví dụ đời thường để nhớ, và quan trọng nhất — cảm nhận chúng cách nhau xa cỡ nào khi n lớn.

1. Bảng tổng quan (từ nhanh đến chậm)​

Big-OTênHình dung đời thường
O(1)hằng sốLấy cuốn sách ở ô đã đánh số sẵn
O(log n)logaritTra từ điển bằng cách mở giữa, bỏ một nửa
O(n)tuyến tínhĐọc lần lượt từng trang một cuốn sách
O(n log n)tuyến-logSắp xếp một bộ bài cho tử tế
O(n²)bậc haiMỗi người bắt tay với mọi người còn lại
O(2ⁿ)mũThử mọi cách bật/tắt của n công tắc

Giờ đi từng lớp một.

2. O(1) — hằng số: không quan tâm n lớn cỡ nào​

Công việc cố định, không phụ thuộc kích thước dữ liệu. Mảng 10 phần tử hay 10 triệu phần tử, lấy phần tử thứ 5 đều một bước.

def lay_phan_tu(A, i):
    return A[i]        # luôn 1 thao tác, dù A to cỡ nào

Ví dụ khác: push/pop trên stack, thêm/xóa đầu danh sách, tra một khóa trong dict. Đây là lớp đáng mơ ước nhất.

3. O(log n) — logarit: mỗi bước bỏ một nửa​

Xuất hiện khi mỗi bước vứt đi một nửa dữ liệu còn lại. Vì n giảm rất nhanh, số bước cực ít.

# Tim trong mang DA SAP XEP bang cach mo giua (binary search)
# Moi buoc loai bo mot nua -> log2(n) buoc

Hình dung: 1 triệu phần tử chỉ cần ~20 bước. Gấp đôi dữ liệu chỉ thêm đúng 1 bước. Gần như miễn phí — luôn nhắm tới khi có thể.

4. O(n) — tuyến tính: chạm mỗi phần tử một lần​

Công việc tỉ lệ thuận với n. Duyệt mảng một lần, tính tổng, tìm max, đếm.

def tong(A):
    s = 0
    for x in A:        # n lan
        s += x
    return s

Đây là lớp "công bằng": n gấp đôi → công việc gấp đôi. Rất nhiều bài toán tốt nhất chỉ có thể đạt O(n) (vì ít nhất phải đọc hết dữ liệu một lần).

5. O(n log n) — tuyến-log: chuẩn của sắp xếp tốt​

Thường gặp ở các thuật toán sắp xếp tốt (merge sort, quick sort): chia dữ liệu thành các nửa (log n tầng), mỗi tầng xử lý toàn bộ n phần tử. n × log n.

Chậm hơn O(n) một chút nhưng vẫn rất tốt — với n = 1 triệu, n log n chỉ gấp ~20 lần n, trong khi n² gấp tận một triệu lần.

6. O(n²) — bậc hai: hai vòng lồng nhau​

Mỗi phần tử "gặp" mọi phần tử khác. Hình dung: trong phòng n người, mỗi người bắt tay với mọi người còn lại → ~n²/2 cái bắt tay.

def in_moi_cap(A):
    for i in A:
        for j in A:     # n * n
            xu_ly(i, j)

Ổn khi n nhỏ, nhưng "đau" nhanh khi n lớn (xem mục 8). Gặp O(n²) trên dữ liệu lớn → tín hiệu nên tìm cách tốt hơn (thường bằng set/dict hoặc sắp xếp).

7. O(2ⁿ) — mũ: thảm hoạ​

Mỗi khi n tăng 1, công việc nhân đôi. Xuất hiện khi thử mọi tổ hợp. Ví dụ: liệt kê mọi tập con của n phần tử có 2ⁿ tập con.

Mũ "chết" nhanh cỡ nào

n = 50 → 2⁵⁰ ≈ một triệu tỷ. Máy chạy 1 tỷ phép/giây cũng cần hơn 12 ngày. n = 60 → hơn 36 năm. Gặp thuật toán mũ là phải tìm hướng khác (thường là quy hoạch động).

8. Nhìn tận mắt: chúng cách nhau xa cỡ nào​

Bấm Run để thấy số thao tác của từng lớp khi n lớn dần:

Đang tải trình chạy code…

Để ý cột O(n^2) ở dòng cuối: với n = 100.000 nó là 10 tỷ, trong khi O(n log n) chỉ ~1,7 triệu. Cùng dữ liệu, khác nhau một trời một vực.

9. 🎮 Trò chơi: Đoán lớp phức tạp​

Đọc tình huống, đoán Big-O. Tính điểm + chuỗi đúng — chơi lại tới khi nắm chắc!

🎮 Đoán lớp phức tạpCâu 1/6· Điểm 0· 🔥 0

Nhớ các hình dung: lấy ở vị trí biết trước = O(1); bỏ một nửa mỗi bước = O(log n); quét một lần = O(n); mọi người với mọi người = O(n²).

Trong phòng n người, mỗi người bắt tay với mọi người còn lại.

10. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Lớp nào KHÔNG phụ thuộc vào kích thước dữ liệu n?
2. Xếp đúng thứ tự từ NHANH đến CHẬM?
3. Vì sao O(2ⁿ) bị coi là "thảm hoạ"?

11. Hoàn thành​

…

☑️ Tiếp theo: 1.2.4 — Big-O vs Big-Θ vs Big-Ω (tốt nhất, xấu nhất, trung bình).