大 O 记号
描述算法随规模 $n$ 增长的上界，忽略常数和低阶项。
| 记号 | 名称 | $n=10^5$ 量级 |
|---|---|---|
| $O(1)$ | 常数 | 极快 |
| $O(\log n)$ | 对数 | 极快 |
| $O(n)$ | 线性 | 通常可行 |
| $O(n \log n)$ | 线性对数 | 排序、分治 |
| $O(n^2)$ | 平方 | $n \le 5000$ 左右 |
| $O(2^n)$ | 指数 | $n \le 20\sim 25$ |
如何估算
- 看最内层循环执行次数
- 递归：写出递推式或层数 × 每层工作量
- 多组数据：注意 $\sum n$ 是否与题目限制一致
空间复杂度
数组开多大、递归栈深度、是否用滚动数组优化 DP。
卡常
同样 $O(n \log n)$，常数差 10 倍可能决定 TLE。见「优化技巧」一章。
例题
例 1：估复杂度是否可行
数据 $n \le 10^5$，双重循环 for i for j 枚举所有点对 → $O(n^2)$ 约 $10^{10}$ 次，必 TLE；应改为排序 + 双指针 $O(n \log n)$ 或哈希 $O(n)$。
例 2：多组数据 $\sum n$
「$T$ 组，每组一条长度为 $n$ 的序列，$\sum n \le 10^5$」：单组可写 $O(n^2)$，但所有组合并不能超过 $10^5$，否则总复杂度爆掉。