Big-O: ký hiệu & trực giác
Big-O là "đơn vị đo" tốc độ thuật toán mà cả thế giới lập trình dùng chung. Sau bài này bạn sẽ nhìn một đoạn code và đoán được nó nhanh hay chậm khi dữ liệu lớn lên — kỹ năng dùng suốt đời lập trình, từ bài tập tới phỏng vấn tới việc thật.
1. Một câu chuyện để hình dung
Tưởng tượng bạn vừa đi làm. Sếp đưa một file và nói: "Tìm xem có hai khách hàng nào có tổng số dư đúng bằng 1 tỷ không."
Hôm nay file có 10 dòng. Bạn viết kiểu "thử mọi cặp" — chạy xong trong một cái chớp mắt. Mọi thứ ổn. Bạn nghĩ: code chạy ngon rồi.
Sáu tháng sau, công ty lớn lên. File giờ có 1 triệu dòng. Vẫn đoạn code đó, nhưng giờ nó chạy... mười mấy phút mới xong một lần. Sếp khó chịu. Bạn hoảng.
Đoạn code không hề thay đổi. Cái thay đổi là dữ liệu lớn lên, và cách code của bạn co giãn theo dữ liệu. Big-O chính là ngôn ngữ để nói về điều đó: khi dữ liệu lớn lên, công việc phình ra nhanh cỡ nào?
Một thuật toán "chạy ổn trên dữ liệu nhỏ" nói lên rất ít. Câu hỏi thật là: nó còn ổn khi dữ liệu gấp nghìn lần không?
2. Big-O nói về XU HƯỚNG, không phải con số chính xác
Ở bài trước ta đếm được đoạn "thử mọi cặp" tốn khoảng
n²/2 phép so sánh. Big-O vứt bỏ những chi tiết vụn và chỉ giữ lại hình dáng của sự tăng trưởng:
n²/2 + 100·n + 5
▲ ▲ ▲
│ │ └── hằng số: khi n lớn, 5 chẳng là gì → bỏ
│ └── số hạng nhỏ hơn: khi n lớn, 100n << n² → bỏ
└── SỐ HẠNG TRỘI: tăng nhanh nhất → GIỮ LẠI
⇒ Big-O = O(n²)
Vì sao được phép "vứt"? Vì Big-O quan tâm n cực lớn. Khi n = 1.000.000:
n²= 1.000.000.000.000 (nghìn tỷ)100·n= 100.000.000 (trăm triệu) — nhỏ hơnn²mười nghìn lần5= 5 — không đáng kể
Số hạng n² áp đảo tất cả. Nên ta gọi cả biểu thức là O(n²). Big-O là cách nói: "khi dữ
liệu đủ lớn, đây mới là thứ quyết định."
Lăng kính quan trọng nhất: "khi n gấp đôi thì sao?"
Đây là cách cảm nhận Big-O dễ nhất. Hỏi: nếu dữ liệu tăng gấp đôi, công việc tăng cỡ nào?
| Big-O | n gấp đôi → công việc | Cảm giác |
|---|---|---|
| O(1) | không đổi | bất biến, sướng nhất |
| O(log n) | +1 chút xíu | gần như miễn phí |
| O(n) | gấp đ ôi | công bằng |
| O(n log n) | gấp đôi + chút | vẫn rất tốt |
| O(n²) | gấp bốn | bắt đầu đau |
| O(2ⁿ) | bình phương lên | thảm hoạ |
3. Hai quy tắc rút gọn (chỉ cần nhớ 2 cái này)
Quy tắc 1 — Bỏ hằng số nhân. O(2n) → O(n); O(n²/2) → O(n²).
Gấp đôi hay chia đôi không đổi hình dáng đường cong — nó chỉ dịch lên xuống. Một thuật toán
"O(2n)" và một thuật toán "O(n)" khi n gấp đôi thì cả hai đều tốn gấp đôi. Cùng họ.
Quy tắc 2 — Giữ số hạng trội. O(n² + n) → O(n²).
Khi n lớn, số hạng lớn nhất nuốt chửng phần còn lại (như đã thấy ở mục 2).
Big-O giống như mô tả một người bằng đặc điểm nổi bật nhất. Bạn không nói "cao 1m75, nặng 68kg, tóc đen, đeo kính, áo xanh" — bạn nói "anh cao nhất phòng". Big-O cũng chỉ giữ đặc điểm tăng trưởng nổi bật nhất.
4. Chạy debug: "nhìn thấy" n² lớn lên
Lý thuyết nói n². Nhưng để cảm được, hãy chạy từng bước đoạn đếm dưới đây với n = 3 và
nhìn biến dem (số lần chạy) phình ra. Bấm ▶ Tự chạy hoặc Tiến ▶:
Bạn vừa thấy: vòng ngoài chạy n lần, mỗi lần kéo theo vòng trong chạy n lần →
n × n = n². Đây là lý do "vòng lặp lồng vòng lặp trên cùng dữ liệu" gần như luôn là O(n²).
5. Các lớp Big-O thường gặp (kèm hình dung)
Xếp từ nhanh nhất đến chậm nhất:
| Big-O | Tên | Hình dung đời thường | Ví dụ |
|---|---|---|---|
| O(1) | hằng số | Lấy cuốn sách ở vị trí đã biết trên kệ | A[5], push/pop stack |
| O(log n) | logarit | Tra từ điển bằng cách mở giữa, bỏ một nửa | tìm kiếm nhị phân |
| O(n) | tuyến tính | Đọc lần lượt từng trang một cuốn sách | duyệt mảng 1 lần |
| O(n log n) | tuyến-log | Sắp xếp một bộ bài tử tế | merge sort, quick sort |
| O(n²) | bậc hai | Bắt tay tất cả mọi người với tất cả mọi người | 2 vòng lặp lồng nhau |
| O(2ⁿ) | mũ | Thử mọi tổ hợp bật/tắt của n công tắc | thử mọi tập con |
Với n = 50, 2⁵⁰ ≈ một triệu tỷ. Một máy tính chạy 1 tỷ phép/giây cũng cần hơn 12 ngày.
Với n = 60 thì cần hơn 36 năm. Thuật toán mũ "chết" rất nhanh — gặp nó là phải tìm cách khác.
(Bài 1.2.3 sẽ mổ xẻ kỹ từng lớp này.)
6. Nhìn code đoán Big-O (chạy thật)
Bấm Run để thấy số lần lặp ứng với từng kiểu code:
Quy tắc nhìn nhanh — cứ áp 4 câu hỏi này:
| Thấy gì trong code | Đoán Big-O |
|---|---|
Không vòng lặp nào phụ thuộc n | O(1) |
Một vòng lặp chạy n lần | O(n) |
Hai vòng lồng nhau, mỗi cái n lần | O(n²) |
| Mỗi bước chia đôi dữ liệu | có log n |
7. Vì sao "chia đôi" lại ra log n?
log₂(n) đơn giản là: "chia n cho 2 bao nhiêu lần thì còn 1?"
1.000.000 → 500.000 → 250.000 → ... → 1
(chỉ khoảng 20 lần chia đôi!)
Mỗi bước vứt đi một nửa → số bước tăng cực chậm so với n. Dữ liệu gấp đôi chỉ thêm
đúng 1 bước. Đó là vì sao O(log n) gần như "miễn phí" và là thứ ta luôn muốn nhắm tới.
| n | log₂(n) ≈ số bước |
|---|---|
| 1.000 | ~10 |
| 1.000.000 | ~20 |
| 1.000.000.000 | ~30 |
8. Cảnh giác: đừng đếm "mấy vòng lặp" một cách máy móc
Vòng lồng nhau không phải lúc nào cũng O(n²). Quan trọng là mỗi vòng chạy bao nhiêu lần
theo n. Ví dụ vòng trong chỉ chạy log n lần:
Vòng ngoài n lần, vòng trong log n lần → O(n log n), không phải O(n²). Luôn hỏi
"vòng này chạy bao nhiêu lần?" thay vì chỉ đếm số vòng.
9. Ba sai lầm hay gặp
- Giữ hằng số. Viết "O(2n)" hay "O(n/2)" — sai chuẩn, đúng phải là O(n).
- Cộng thay vì lấy trội. "O(n² + n)" → phải rút thành O(n²).
- Đếm vòng lặp mù quáng. Hai vòng lồng nhau chưa chắc O(n²) (xem mục 8); một vòng v ẫn có thể là O(n²) nếu bên trong gọi một hàm O(n).
10. 🎮 Trò chơi: Đoán Big-O
Nhìn đoạn code, đoán Big-O của nó. Có tính điểm và chuỗi đúng — chơi tới khi đúng hết thì thôi!
11. Quiz kiểm tra nhanh
12. Hoàn thành
…☑️ Tiếp theo: 1.2.3 — Các lớp phức tạp thường gặp (đào sâu O(1) → O(2ⁿ) với ví dụ cho từng lớp).