Giới hạn bài toán
27/04/2026, 12:59:14Giới hạn độ phức tạp và kích thước N
Bảng dưới đây cung cấp ước lượng kích thước N tương ứng với từng độ phức tạp thuật toán trong khoảng thời gian ~2s.
| Độ phức tạp | Giới hạn N thông dụng | Giới hạn N MAX |
|---|---|---|
| \(N^4\) | 100 | 250 - 300 |
| \(N^3\) | 500 | 2000 - 3000 |
| \(\frac{N^3}{64}\) | 2000 | 8000 - 10000 |
| \(N^2\) | 20000 | 150000 - 200000 |
| \(\frac{N^2}{64}\) | 100000 | 300000 - 500000 |
| \(N\sqrt{N}\log N\) | 50000 | 200000 |
| \(N\sqrt{N}\) | 200000 | 2000000 - 3000000 |
| \(N\log N\) | 400000 | 3000000 - 5000000 |
| \(N\) | 2000000 | \(10^8 - 10^{10}\) |
N MAX là giá trị N trong trường hợp bạn tối ưu rất tốt (sử dụng mọi kỹ thuật có thể và bài toán tương đối “dễ tối ưu”).
Time limit tham khảo: khoảng 2 giây.