时间复杂度和算法选择

数据范围    时间复杂度    算法选择    
n \leq 30    指数级别   O(2^n)    深度优先搜索（DFS）+ 剪枝、状态压缩动态规划    
n \leq 100    O(n^3)    Floyd 算法、动态规划、高斯消元    
n \leq 1000    O(n^2) 、  O(n^2 \log n)    动态规划、二分查找、朴素版 Dijkstra、朴素版 Prim、Bellman-Ford    
n \leq 10000    O(n \sqrt{n})    块状链表、分块、莫队    
n \leq 100000    O(n \log n)    快速排序、线段树、树状数组、堆、拓扑排序、Dijkstra + 堆、Prim + 堆、Kruskal、SPFA、凸包、半平面交    
n \leq 1000000    O(n) 、常数较小的   O(n \log n)    单调队列、哈希、双指针扫描、BFS、并查集、KMP、AC 自动机    
n \leq 10000000    O(n)    双指针扫描、KMP、AC 自动机、线性筛素数    
n \leq 10^9    O(\sqrt{n})    判断质数    
n \leq 10^{18}    O(\log n)    最大公约数、快速幂、数位 DP    
n \leq 10^{1000}    O((\log n)^2)    高精度加减乘除    
n \leq 10^{100000}    O(\log k \cdot \log \log k)    高精度加减、FFT/NTT