复杂度再练

看代码结构就能报复杂度，这是估算"能不能过"的基本功。常见对应：一层循环 $O(n)$；两层嵌套 $O(n^2)$；每次把规模砍一半（二分、快速幂）$O(\log n)$；排序 $O(n\log n)$。图的 BFS/DFS 遍历，每个点进出一次、每条边看一次，是 $O(n+m)$（别错记成 $O(n^2)$，那是邻接矩阵的遍历）。

for (int i = 0; i < n; i++)           // O(n)
    for (int j = 0; j < n; j++)       // 再套一层 -> O(n^2)
        work();

while (l < r) { int mid = (l+r)/2; }  // 每次砍半 -> O(log n)

估算方法：把各层循环的执行次数相乘，再看最大的那项。实战经验：现在的评测机大约每秒能跑 $10^8$ 次简单运算。据此对着数据范围反推——$n\le 10^6$ 只能用 $O(n)$ 或 $O(n\log n)$；$n\le 10^3$ 可以 $O(n^2)$；$n\le 20$ 往往要 $O(2^n)$ 的搜索。坑：别纠结 $\log$ 的底是 $2$ 还是 $10$（只差常数、不影响量级），也别漏算藏在函数里的循环。