yxc大佬总结的经验，你们可以根据数据范围来选择合适的算法，打比赛很有用
一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 1e7∼1e8
为最佳。
下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：
| 时间复杂度 | 常用算法 |
|---|---|
| N≤30 => 指数级别 | dfs+剪枝，状态压缩dp |
| N≤100 => O(N3) | floyd，dp，高斯消元 |
| N≤1000 => O(N2)，O(N2logN) | dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford |
| N≤10000 => O(N∗√N)， | 块状链表、分块、莫队 |
| N≤100000 => O(NlogN) | 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分 |
| N≤1000000 => O(N)以及常数较小的 O(NlogN) 算法 | 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn)的做法：sort、树状数组、heap、dijkstra、spfa |
| N≤10000000=> O(N) | 双指针扫描、kmp、AC自动机、线性筛素数 |
| N≤1e9=> O(√N) | 判断质数 |
| N≤1e18=> O(logN) | 最大公约数，快速幂, 二分 |
| N≤1e1000 => O(k) | 高精度加减乘除 |
| N≤10100000=> O(logK×loglogK) | k表示位数，高精度加减、FFT/NTT |
0 comments
No comments so far...