从数据范围判断算法方向

数据范围是一种提示语言

如果 $n$ 只有 $20$ 左右，枚举子集可能是自然选择；如果 $n$ 达到 $10^5$，$O(n^2)$ 通常就需要重新审视。读到范围时，可以先做一个粗略估算：程序大约需要执行多少次基本操作？

常见的方向包括：

• $O(n)$：线性扫描、前缀和、双指针；
• $O(n\log n)$：排序、平衡树、分治；
• $O(n^2)$：通常适合几千以内的数据；
• $O(2^n)$：通常只适合较小的 $n$，常与状态压缩或搜索结合。

不要只看最坏的符号

同样是 $O(n)$，一次简单加法和一次复杂哈希操作的常数不同；同样是 $O(n\log n)$，排序与树结构的内存访问特征也不同。实际判断还要结合语言、内存限制和数据分布。

但在学习阶段，先用复杂度排除明显不可能的方案，再讨论常数优化，通常是更稳妥的顺序。