算法时间复杂度分析
对于时间限制为[1\text{s},2\text{s}]的题目，C++代码中的操作次数应控制在[10^7,10^8]为最佳。
| 数据范围 | 时间复杂度 | 算法 |
|---|---|---|
| $n≤30$ | 指数级别 | dfs+剪枝、状态压缩dp |
| $n≤100$ | $O(n^3)$ | floyd、dp、高斯消元 |
| $n≤1000$ | $O(n^2),O(n^2\log n)$ | dp、二分、朴素dijkstra、朴素prim、Bellman-Ford |
| $n≤10^4$ | $O(n\sqrt n)$ | 块状链表、分块 |
| $n≤10^5$ | $O(n\log n)$ | sort、线段树、树状数组、set/map、heap、dijkstra+heap、spfa |
| $n≤10^6$ | ① $O(n)$ ② 常数比较小的 $O(n\log n)$ |
① 单调队列、hash、双指针、bfs、并查集、kmp、AC自动机 ② sort、树状数组、heap、dijkstra+heap、spfa |
| $n≤10^7$ | $O(n)$ | 双指针、kmp、AC自动机、线性筛素数 |
| $n≤10^9$ | $O(\sqrt n)$ | 判断质数 |
| $n≤10^{18}$ | $O(\log n)$ | 欧几里得算法、快速幂、数位dp |