Chọn thuật toán theo ràng buộc — ước lượng độ phức tạp theo lũy thừa của 10

Bài chuẩn dừng ở việc TÍNH $O(...)$ của một thuật toán đã cho sẵn. Ở đây đề không cho thuật toán nào cả — chỉ cho `n` và giới hạn thời gian, em phải tự dựng cả bảng ngưỡng rồi tra ngược, một thao tác đòi hỏi hiểu bản chất Big-O chứ không chỉ tính theo công thức.

Với ngân sách $B = 10^8$ và giới hạn 1 giây, ngưỡng `n` của mỗi lớp là nghiệm lớn nhất của $f(n) \le B$. Dò chính xác bằng chặt nhị phân trên `n` (vì $f$ tăng đơn điệu), không đoán: ```python def max_n_binary_search(op_count, budget=10**8, lo=1, hi=10**18): """n lon nhat sao cho op_count(n) <= budget (op_count khong giam theo n). Mac dinh budget = 10**8 -- viet lai gia tri (thay vi tham chieu hang so BUDGET o module-level) de khoi code nay TU DAY DU khi trich rieng ra lam vi du cho hoc sinh, khong phu thuoc ten bien ngoai pham vi ham.""" best = lo - 1 while lo <= hi: mid = (lo + hi) // 2 if op_count(mid) <= budget: best = mid lo = mid + 1 else: hi = mid - 1 return best ```

$O(n!)$: $n \le 11$ ($11! \approx 3{,}99 \times 10^7$). $O(2^n)$: $n \le 26$ ($2^{26} \approx 6{,}71 \times 10^7$). $O(n^3)$: $n \le 464$. $O(n^2)$: $n \le 10,000$. $O(n\log n)$: $n \le 4,523,071$ (xấp xỉ $4{,}5 \times 10^6$). $O(n)$: $n \le 100,000,000$.

Bảng kinh nghiệm quen thuộc nói $n \le 10$ cho $O(n!)/O(2^n)$, $n \le 20$–$22$ cho $O(2^n)$, $n \le 500$ cho $O(n^3)$, $n \le 5000$ cho $O(n^2)$, $n \le 10^6$ cho $O(n\log n)$, $n \le 10^8$ cho $O(n)$. So với con số dò chính xác ở trên, phần lớn bảng kinh nghiệm **thấp hơn** ngưỡng thật — đó là biên an toàn có chủ đích, vì một đề thi thật thường chạy nhiều test/subtask liên tiếp chứ không phải đúng một lần, và hằng số ẩn của cách cài đặt cụ thể luôn lớn hơn 1 chút ít. Riêng $O(n^3)$ là một ngoại lệ đáng chú ý: $500^3 = 1{,}25 \times 10^8$ — bản thân con số 500 đã VƯỢT ngân sách $10^8$ gần một phần tư, nên đây là quy ước làm tròn hơi lạc quan, không phải một biên an toàn. Ngưỡng dò chính xác (464) mới thật sự nằm trong ngân sách.

Ta có ngân sách $B = 10^8$ phép tính cho 1 giây. Với lớp $O(n^3)$, giải $n^3 \le 10^8 \Leftrightarrow n \le \sqrt[3]{10^8} \approx 464{,}16$, nên $n$ lớn nhất thỏa mãn là $n = 464$. Vậy một thuật toán $O(n^3)$ chỉ thật sự an toàn khi đề cho $n$ không vượt quá 464 — dùng mốc "500" cho lớp này cần thêm một biên dự phòng, vì bản thân 500 đã sát hoặc vượt ngân sách.

Nhỏ hơn cả ngưỡng $O(n!)$ (11) một chút và nằm sâu trong ngưỡng $O(2^n)$ (26) — dấu hiệu đề đang cho phép duyệt toàn bộ tập con hoặc hoán vị (vét cạn có kiểm soát), một việc chỉ khả thi với `n` cực nhỏ.

Vượt xa ngưỡng $O(n^3)$ (464) nên một thuật toán ba tầng vòng lặp lồng nhau chắc chắn TLE. Ngưỡng $O(n^2)$ (10.000) còn dư nhiều — đây là lớp rộng nhất còn an toàn cho `n` cỡ này.

Vượt xa ngưỡng $O(n^2)$. Ngưỡng $O(n\log n)$ (khoảng 4,5 triệu) còn dư rất nhiều — dấu hiệu đề đang chờ một thuật toán sắp xếp, hoặc một cấu trúc dữ liệu xử lý truy vấn theo $\log n$ mỗi lần.

Ngay cả $O(n)$ đơn thuần ($10^9$ phép tính) đã VƯỢT ngân sách $10^8$ tới 10 lần — một vòng lặp duyệt hết `n` phần tử theo nghĩa đen là không kịp giờ. Đề đang chờ một công thức đóng, hoặc một thuật toán $O(\sqrt{n})$/$O(\log n)$.

Ngay cả $O(\sqrt{n})$ ($10^9$) cũng đã vượt ngân sách. Chỉ còn lớp $O(\log n)$ (khoảng 60 phép tính, vì $\log_2 10^{18} \approx 60$) hoặc $O(1)$ là chắc chắn kịp giờ — dấu hiệu rõ ràng của công thức đóng hoặc lũy thừa nhanh (bình phương liên tiếp).

Tra bảng ngưỡng Ví dụ 1 theo thứ tự từ hẹp đến rộng: $n \le 15$ ứng với $O(2^n)/O(n!)$; $n \le 1.000$ ứng với $O(n^2)$ (vì đã vượt ngưỡng $O(n^3)=464$); $n \le 10^5$ ứng với $O(n\log n)$ (vì đã vượt ngưỡng $O(n^2)=10.000$); $n \le 10^9$ và $n \le 10^{18}$ đều chỉ còn $O(\log n)$ hoặc $O(\sqrt{n})$ là an toàn, vì cả hai đã vượt ngưỡng $O(n) = 10^8$. Vậy quy trình là: so `n` của đề với TỪNG ngưỡng trong bảng, từ lớp phức tạp cao nhất xuống thấp nhất, và dừng ở lớp ĐẦU TIÊN mà `n` đề bài còn nằm trong ngưỡng cho phép.

Bài chuẩn chỉ có một `n`. Ở đây một thuật toán đồ thị điển hình — tiền xử lý một lần rồi trả lời từng truy vấn — có độ phức tạp phụ thuộc CẢ BA đại lượng $V$, $E$, $q$ cùng lúc, và ghép sai công thức (nhân hết mọi thứ với nhau) sẽ cho một con số sai lệch khủng khiếp so với thực tế.

Giả sử thuật toán tiền xử lý tốn $O((V+E)\log V)$ (kiểu Dijkstra/BFS có hàng đợi ưu tiên), rồi mỗi truy vấn tốn thêm $O(\log V)$. Tổng chi phí là $O((V+E)\log V + q\log V)$ — CỘNG hai phần việc tách biệt (tiền xử lý MỘT LẦN, và $q$ truy vấn SAU ĐÓ), không nhân chúng vào nhau vì chúng không lồng nhau.

Với $V = 10^5$, $E = 10^6$, $q = 10^5$: $(V+E)\log_2 V + q\log_2 V \approx 19,931,569$ phép tính — nằm gọn trong ngân sách $10^8$, khả thi.

Nếu nhầm coi cả ba đại lượng đều lồng nhau và viết $O(V \cdot E \cdot q)$: thay số cho $V \cdot E \cdot q = 10,000,000,000,000,000$ — lớn hơn ngân sách gấp hàng trăm triệu lần. Ước lượng kiểu này khiến em tưởng nhầm một thuật toán hoàn toàn khả thi là bất khả thi, rồi bỏ lỡ cách làm đúng, hoặc ngược lại tưởng nhầm một thuật toán chậm là chấp nhận được vì "cứ nhân đại cho chắc".

Ta có tổng chi phí $O((V+E)\log V + q\log V)$ do hai giai đoạn (tiền xử lý và trả lời truy vấn) độc lập, CỘNG với nhau chứ không nhân. Thay $V=10^5, E=10^6, q=10^5$: kết quả xấp xỉ $19,931,569$, nhỏ hơn ngân sách $10^8$ nên thuật toán khả thi. Vậy khi đề có nhiều ràng buộc, việc đầu tiên là xác định các đại lượng đó CỘNG hay NHÂN vào nhau trong công thức độ phức tạp thật, dựa trên cấu trúc thật của thuật toán — không suy đoán theo cảm tính.