Ước lượng giới hạn bài toán

Một trong những kỹ năng quan trọng nhất: nhìn vào ràng buộc của bài và biết ngay cần thuật toán có độ phức tạp bao nhiêu.

Quy tắc vàng

Máy tính hiện đại thực hiện khoảng ${10}^8$ — ${10}^9$ phép tính đơn giản mỗi giây. Với time limit 1 giây, số phép tính tối đa khoảng ${10}^8$.

Bảng tra cứu nhanh

Ví dụ thực tế

Ràng buộc: $N\le 2\times {10}^5$, time limit 1 giây.

$O(N^2)$ → $4\times {10}^{10}$ phép tính → quá chậm ❌
$O(N\log N)$ → $\approx 3.4\times {10}^6$ phép tính → ổn ✓

Ràng buộc: $N\le 500$, time limit 2 giây.

$O(N^3)$ → $1.25\times {10}^8$ phép tính → vừa đủ ✓

Cẩn thận với hằng số

Big-O bỏ qua hằng số, nhưng trong thực tế hằng số quan trọng:

• Thao tác với unordered_map trong C++ tuy $O(1)$ nhưng hằng số lớn.
• Python chậm hơn C++ khoảng 10-50 lần → với Python cần ước lượng thêm.

Ước lượng cho Python

Quy trình khi đọc đề

1. Đọc ràng buộc $N$.
2. Tra bảng → xác định độ phức tạp cần thiết.
3. Nghĩ thuật toán phù hợp.
4. Ước lượng chính xác hơn nếu cần.