时空复杂度

📚 看题先看数据范围——范围就是提示，据此推出可用算法，再看题干基本就能锁定做法。这里先建复杂度直觉，完整板子表见 01-根据时间复杂度选择算法。

时间复杂度分析

一般 ACM 或者笔试题的时间限制是 1 秒或 2 秒。在这种情况下，C++ 代码中的操作次数控制在 \(10^7\) 为最佳。

数据范围	复杂度	可用算法
\(n \le 30\)	指数级别	dfs + 剪枝、数字排列、n 皇后、八数码；状态压缩 dp、蒙德里安的梦想、最短 Hamilton 路径
\(n \le 100\)	\(O(n^3)\)	floyd、dp
\(n \le 1000\)	\(O(n^2)\)、\(O(n^2 \log n)\)	dp、二分、朴素版 dijkstra、朴素版 prim、Bellman-Ford
\(n \le 10000\)	\(O(n\\sqrt{n})\)	块状链表、分块、莫队
\(n \le 100000\)	\(O(n \log n)\)	sort、线段树、树状数组、set/map、heap、dijkstra+heap、prim+heap、spfa、凸包、半平面交、二分
\(n \le 10^6\)	\(O(n)\)、常数较小的 \(O(n \log n)\)	hash、双指针、并查集、kmp、AC 自动机
\(n \le 10^7\)	\(O(n)\)	双指针、kmp、AC 自动机、线性筛素数
\(n \le 10^9\)	\(O(\\sqrt{n})\)	判断质数
\(n \le 10^{18}\)	\(O(\log n)\)	最大公约数、快速幂
\(n \le 10^{1000}\)	\(O((\log n)^2)\)	高精度加减乘除
\(n \le 10^{100000}\)	\(O(\log n \cdot \log \log n)\)	高精度加减、FFT/NTT

常数较小的 \(O(n \log n)\)：sort、树状数组、heap、dijkstra、spfa。

一般来说，k 重循环，算法时间复杂度就是 \(n^k\)：

spfa 算法、匈牙利算法、最大流算法时间复杂度理论值很大，但是实际运行速度很快：

动态规划问题的计算量 = 状态数量 × 状态转移的计算量：

题目一般给 64M：

1 Byte = 8 bit；1 KB = 1024 Byte；1 MB = 1024×1024 Byte；1 GB = 1024×1024×1024 Byte
bool：1 Byte；char：1 Byte
int：4 Byte，\(2^{31} \approx 2 \times 10^9\)（2147483648，10 位 10 进制）
double / long long：8 Byte，\(2^{63} \approx 9 \times 10^{18}\)（9223372036854775807，19 位 10 进制）
long double：16 Byte
__int128：\(10^{38}\)（85070591730234615865843651857942052864，38 位 10 进制）

递归也是需要空间的——递归调用了系统栈。快速排序使用了递归，所以空间复杂度是 \(O(\log n)\)。