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 — 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 .
Bảng tra cứu nhanh
| Ràng buộc | Độ phức tạp tối đa | Thuật toán gợi ý |
|---|---|---|
| Duyệt hoán vị | ||
| hoặc | Bitmask DP | |
| Floyd-Warshall, DP bậc 3 | ||
| DP bậc 2, brute force | ||
| hoặc | Sort, BFS/DFS, Segment Tree | |
| hoặc | Linear scan, prefix sum | |
| hoặc | Tìm kiếm nhị phân, math | |
| Tìm kiếm nhị phân, fast power |
Ví dụ thực tế
Ràng buộc: , time limit 1 giây.
→ phép tính → quá chậm ❌
→ phép tính → ổn ✓
Ràng buộc: , time limit 2 giây.
→ 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_maptrong C++ tuy 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
| Time limit | C++ tối đa | Python tối đa |
|---|---|---|
| 1 giây | ||
| 2 giây |
Quy trình khi đọc đề
- Đọc ràng buộc .
- Tra bảng → xác định độ phức tạp cần thiết.
- Nghĩ thuật toán phù hợp.
- Ước lượng chính xác hơn nếu cần.
Bình luận