常见复杂度对照

记住这张“数据规模 → 允许复杂度”的对照表，拿到题一眼就能反推该用什么算法（按一秒 $10^8$ 估）：

• $n\le 20$：$O(2^n)$ 或 $O(n!)$，可以爆搜、状压；
• $n\le 500$：$O(n^3)$，三层循环、Floyd；
• $n\le 5000$：$O(n^2)$，两层循环、朴素 DP；
• $n\le 10^5$：$O(n\log n)$，排序、二分、堆；
• $n\le 10^6$ 甚至更大：$O(n)$ 或 $O(n\log n)$，线性扫描、前缀和。

反过来用更好使：看到 $n=100$ 就知道可以放心写 $O(n^3)$；看到 $n=10^6$ 就知道两层循环必死，得想线性做法。

// n = 10^6, 只能线性
long long sum = 0;
for (int i = 0; i < n; i++) sum += a[i];   // O(n)

坑：这只是数量级参考，常数大小、多组数据、时限松紧都会影响结果。$O(n\log n)$ 里的 $\log$ 一般当作 $20$ 左右来估。