不同测试数据下，该如何选择算法

一般情况下，程序每秒能处理的操作次数大概是 10的8次左右。所以我们要根据数据范围n，选择操作次数不超过这个阈值的算法，避免超时。

分范围速记

小数据量（n ≤ 30）

时间复杂度：指数级别（不用纠结具体多少，能跑通就行）

推荐算法：DFS+剪枝、状态压缩DP

备注：数据量极小，哪怕是指数级算法也能轻松跑通，重点是剪枝优化，减少无效操作。

小到中等数据量（n ≤ 100）

时间复杂度：O(n3)推荐算法：Floyd算法（求多源最短路）、三维DP、高斯消元

备注：1003=106，远低于108，完全无压力。

中等数据量（n ≤ 10³）

时间复杂度：O(n2)、O(n2logn)推荐算法：朴素版Dijkstra、朴素版Prim、Bellman-Ford、二维DP、二分查找

备注：10002=106，即使加个logn，也能轻松跑过。

中等偏大数据量（n ≤ 10⁴）

时间复杂度：O(nn​)推荐算法：分块、莫队算法、块状链表

备注：104×100=106（104​=100），刚好卡在舒适区，这类算法专门适配这个数据范围。

大数据量（n ≤ 10⁵）

时间复杂度：O(nlogn)推荐算法：各种排序（sort）、线段树、树状数组、set/map、堆优化Dijkstra、堆优化Prim、Kruskal、拓扑排序、SPFA、CDQ分治、整体二分、后缀数组、树链剖分、动态树

备注：刷题最常遇到的范围！105×20≈2×106（log2(10^5)≈17），完全符合每秒处理上限，这些算法一定要熟练掌握。

超大数据量（n ≤ 10⁶）

时间复杂度：O(n)、常数较小的O(nlogn)推荐算法：单调队列、哈希、双指针扫描、BFS、并查集、KMP、AC自动机；低常数O(nlogn)：sort、树状数组、堆、Dijkstra、SPFA

备注：106 级别需要控制常数，避免冗余操作，优先选线性时间算法。

极大数据量（n ≤ 10⁷）

时间复杂度：严格O(n)推荐算法：双指针扫描、KMP、AC自动机、线性筛素数

备注：107 已经接近处理上限，必须用严格线性算法，任何多余的操作都可能超时。

巨量数据（n ≤ 10⁹）

时间复杂度：O(n​)推荐算法：试除法判断质数

备注：109​≈3×104，操作次数极少，高效快捷。

超大整数（n ≤ 10¹⁸）

时间复杂度：O(logn)推荐算法：快速幂、最大公约数（欧几里得算法）、数位DP

备注：数据极大，但logn后操作次数极少（log2(10^18)≈60），核心是利用对数级算法降维。

超高精度（n ≤ 10¹⁰⁰⁰）

时间复杂度：O((logn)2)推荐算法：高精度加减乘除

备注：这里的n是高精度数的位数，核心是处理大数运算，时间复杂度和位数的平方成正比。

超高精度（n ≤ 10⁵位）

时间复杂度：O(logk×loglogk)（k为位数）

推荐算法：高精度加减、FFT/NTT（优化高精度乘法）

备注：位数极多，普通高精度乘法会超时，需要用FFT/NTT优化，降低时间复杂度。

刷题时，先看数据范围n，再对应找时间复杂度，最后锁定算法——这个逻辑能帮你节省大量思考时间，避免走弯路。

刷题时遇到不确定的情况，随时查阅；熟练之后，看到n的范围就能条件反射出对应的算法。