数据范围与实际复杂度的关系 - 杂记 | duoxichangan = 其实连按部就班也比想象中难

对于比赛的评测，一般一秒能运行 $5 \times 10^8$ 次运算

数据范围	时间复杂度级别	适用算法
$n \le 30$	指数级别	$dfs$ （剪枝）、状压 $dp$
$n \le 100$	$O(n^3)$	$floyd$ 、 $dp$ 、高斯消元
$n \le 10^3$	$O(n^2)、O(n^2·log{(n)})$	$dp$ 、二分、 $Dijkstra$ 、 $Prim$ 、 $Bellman-Ford$
$n \le 10^4$	$O(n \times \sqrt{n})$	块状链表、分块、莫队
$n \le 10^5$	$O(n \times log(n))$	排序、线段树、树状数组、 $set$ 、 $map$ 、 $heap$ 、拓扑排序，堆优化的 $Dijkstra$ 、堆优化的 $prim$ 、 $Kruskal$ 、 $Spfa$ 、求凸包、求半平面交、二分、 $CDQ$ 分治、二分、后缀数组、树链剖分、动态树
$n \le 10^6$	$O(n)$ 或者小常数 $O(n \times log(n))$	单调队列、 $hash$ 、双指针、 $BFS$ 、并查集、 $kmp$ 、 $AC$ 自动机、 $sort$ 、树状数组、 $heap$ 、 $Dijkstra$ 、 $Spfa$
$n \le 10^7$	$O(n)$	双指针、 $KMP$ 、 $AC$ 自动机、线性筛素数
$n \le 10^9$	$O(\sqrt{n})$	判断质数
n \le 10^	$O(log(n))$	最大公约数、快速幂、数位 $dp$
$...$		~~高精度~~