Wiki › Độ phức tạp › Ước lượng giới hạn bài toán

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

huunguyen Updated Tháng tư 3, 2026

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

Ràng buộc $N$	Độ phức tạp tối đa	Thuật toán gợi ý
$N \leq 10$	$O (N!)$	Duyệt hoán vị
$N \leq 20$	$O (2^{N})$ hoặc $O (2^{N} \cdot N)$	Bitmask DP
$N \leq 100$	$O (N^{3})$	Floyd-Warshall, DP bậc 3
$N \leq 1000$	$O (N^{2})$	DP bậc 2, brute force
$N \leq 10^{5}$	$O (N \log N)$ hoặc $O (N)$	Sort, BFS/DFS, Segment Tree
$N \leq 10^{6}$	$O (N)$ hoặc $O (N \log N)$	Linear scan, prefix sum
$N \leq 10^{9}$	$O (\sqrt{N})$ hoặc $O (\log N)$	Tìm kiếm nhị phân, math
$N \leq 10^{18}$	$O (\log N)$	Tìm kiếm nhị phân, fast power

Ví dụ thực tế

Ràng buộc: $N \leq 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 \leq 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

Time limit	C++ tối đa	Python tối đa
1 giây	$10^{8}$	$10^{7}$
2 giây	$2 \times 10^{8}$	$2 \times 10^{7}$

Quy trình khi đọc đề

Đọc ràng buộc $N$ .
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.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0