时间复杂度

算法的最基础的内容就是时间复杂度。时间复杂度很好理解就是测量算法的效率，空间复杂度测量的是算法的内存占用量。

表达时间复杂度或空间复杂度往往用的是 Big O notation，比如 $O(n^2)$。这些只是一种粗略的复杂度计算方法，它只取复杂度中最高的一项。

比如 $O(2n^3+3n+1)$ 实际上等同于 $O(n^3)$，

通过题目的数据量大小，推断出时间复杂度，再通过时间复杂度推断出解题的优化算法。

以下是一个来自Acwing的总结表，它描述了所给予的数据量范围与时间复杂度和解题算法的关系：

1. ( n \leq 30 ) = 指数级别 , dfs + 剪枝，状态压缩 dp
2. ( n \leq 100 ) = ( O(n^3) ) , floyd，dp，高斯消元
3. ( n \leq 1000 ) = ( O(n^2) ) , ( O(n^2 \log n) ) dp，二分，朴素版 Dijkstra、朴素版 Prim、Bellman-Ford
4. ( n \leq 10000 ) = ( O(n \sqrt{n}) ) , 块状链表、分块、莫队
5. ( n \leq 100000 ) = ( O(n \log n) ) , 各种 sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra + heap、prim + heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ 分治、整体二分、后缀数组、树链剖分、动态树
6. ( n \leq 1000000 ) = ( O(n) ) 常数较小的 ( O(n \log n) ) 算法 ，单调队列、hash、双指针扫描、BFS、并查集，kmp、AC 自动机 ，常数较小的 ( O(n \log n) ) 做法：sort、树状数组、heap、dijkstra、spfa
7. ( n \leq 10000000 ) = ( O(n) ) ， 双指针扫描、kmp、AC 自动机、线性筛素数
8. ( n \leq 10^9 ) = ( O(\sqrt{n}) ) 判断质数
9. ( n \leq 10^{18} ) = ( O(\log n) ) 最大公约数，快速幂，数位 DP
10. ( n \leq 10^{1000} ) = ( O((\log n)^2) ) 高精度加减乘除
11. ( n \leq 10^{100000} ) = ( O(\log k \times \log \log k) )，( k ) 表示位数
    高精度加减、FFT/NTT