利用数据范围估计时间复杂度¶
一般题目的时间限制是 1 秒或 2 秒，C++ 代码中的操作次数控制在 \(10^7 \sim 10^8\) 为最佳。
| 复杂度 | 数量级 | 最大规模 |
|---|---|---|
| \(O(\log N)\) | \(\gg 10^{20}\) | 很大 |
| \(O(\sqrt{N})\) | \(10^{12}\) | \(10^{14}\) |
| \(O(N)\) | \(10^6\) | \(10^7\) |
| \(O(N \log N)\) | \(10^5\) | \(10^6\) |
| \(O(N^2)\) | \(1000\) | \(2500\) |
| \(O(N^3)\) | \(100\) | \(500\) |
| \(O(N^4)\) | \(50\) | \(50\) |
| \(O(2^N)\) | \(20\) | \(20\) |
| \(O(N!)\) | \(9\) | \(10\) |
参考：