一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下,C++代码中的操作次数控制在 107∼108 为最佳。
下面给出在不同数据范围下,代码的时间复杂度和算法该如何选择:
数据范围 |
时间复杂度 |
算法选择 |
n≤30 |
指数级别 |
DFS+剪枝、状态压缩DP |
n≤100 |
O(n3) |
Floyd、DP、高斯消元 |
n≤1000 |
O(n2)、O(n2logn) |
DP、二分、朴素版Dijkstra、朴素版Prim、Bellman-Ford |
n≤10000 |
O(nn) |
块状链表、分块、莫队 |
n≤100000(105) |
O(nlogn) |
各种Sort、线段树、树状数组、Set/Map、Heap、拓扑排序、堆优化版Dijkstra、堆优化版Prim、Kruskal、SPFA、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树 |
n≤1000000(106) |
O(n) 常数较小的 O(nlogn) |
单调队列、Hash、双指针扫描、并查集,kmp、AC自动机 Sort、树状数组、Heap、Dijkstra、SPFA |
n≤10000000(107) |
O(n) |
双指针扫描、KMP、AC自动机、线性筛素数 |
n≤109 |
O(n) |
判断质数 |
n≤1018 |
O(logn) |
最大公约数、快速幂、数位DP |
n≤101000 |
O((logn)2) |
高精度加减乘除 |
n≤10100000 |
O(logk⋅loglogk), k 表示位数 |
高精度加减、FFT/NTT |
评论区