数据结构与算法 / 系统课时

根据数据规模估算复杂度上限

根据数据规模估算复杂度上限

拿到题目后,先看数据规模再想算法,能在几秒内淘汰大量不可能通过的方案。本篇建立“规模 → 运算量 → 可接受复杂度”的估算方法,并说明多维输入、常数和语言差异带来的边界。

学习目标

  • 能根据 n 的数量级快速排除明显过慢的算法。
  • 能估算常见复杂度在给定规模下的大致运算量。
  • 能识别多组测试、排序、哈希和高常数操作对估算结果的影响。

先把复杂度换成数量级

复杂度不是抽象标签,它最终要落到大致操作次数。若 n = 100000,那么 n2=1010n^2 = 10^{10},通常已经远超普通在线评测希望你在短时间内完成的工作量;而 nlog⁡nn\log n 约为几百万量级,往往仍有机会通过。

下面的表适合做第一轮筛选,而不是当成绝对判定标准。实际限制还受语言、常数、内存访问、评测机和时限影响。

最大规模 优先考虑的复杂度 典型方向
n <= 20 O(2n)O(2^n)、O(n2n)O(n2^n) 枚举子集、状态压缩
n <= 100 O(n3)O(n^3) 或更低 三重循环、区间 DP
n <= 1000 O(n2)O(n^2) 或更低 两两关系、二维 DP
n <= 100000 O(nlog⁡n)O(n\log n)、O(n)O(n) 排序、二分、堆、哈希、双指针
n >= 1000000 通常优先 O(n)O(n) 线性扫描、计数、流式处理

用约束直接否掉暴力方案

假设题目给出 n <= 100000,要求判断是否存在满足条件的元素对。最直接的双重循环需要检查大约 n2/2n^2/2 个组合,数量级接近 5×1095\times10^9,应在编码前就否掉。

这时应继续追问:能否用哈希表把“查另一个元素”降为平均 O(1)O(1),能否排序后用双指针得到 O(nlog⁡n)O(n\log n),或者题目是否具有可供二分的单调性。复杂度估算的作用不是替你选算法,而是缩小候选范围。

反过来,若 n <= 20,枚举所有子集只有约 220≈1062^{20} \approx 10^6 个状态,指数算法反而可能是正确方向。看到“指数”就拒绝,和看到“线性”就接受一样,都是脱离数据规模谈复杂度。

别只看一个 n

很多题的真实规模不是单个变量。矩阵遍历的成本是行数与列数的乘积;两组数组做两两比较是 O(nm)O(nm);多组测试则要关注所有测试数据的总规模。

例如单组 n <= 2000 时,O(n2)O(n^2) 约为四百万次操作,可能可行;但如果有 100 组都达到上限,总工作量就会放大两个数量级。题面若给出“所有测试用例的 n 之和不超过某值”,应优先使用这个总约束估算。

还要把隐藏步骤算进去。主循环是 O(n)O(n),但如果前面必须排序,总复杂度就是 O(nlog⁡n)O(n\log n);哈希表查找平均是 O(1)O(1),但存在常数与退化风险;递归搜索若重复访问同一状态,也可能从可接受的状态数膨胀到指数级。

建立一个十秒复杂度检查

拿到题目后,可以固定做四次判断:

  1. 找到最大输入规模,确认是否存在多组测试或多个维度。
  2. 写出最直观方案的复杂度,并代入最大规模估算数量级。
  3. 如果数量级明显过大,寻找能降低一层循环或减少状态数量的结构。
  4. 选定方案后,再把排序、哈希、递归深度和额外空间一起纳入判断。

例如 n = 100000 时,双重循环的 101010^{10} 级操作应立刻触发“必须降复杂度”的警报;而排序后的几百万级比较通常值得继续实现和验证。

复杂度估算最重要的结果不是背下一张阈值表,而是形成条件反射:先用数据规模限制算法空间,再开始写代码。这样能显著减少“实现完整后才发现超时”的无效刷题时间。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

根据数据规模估算复杂度上限

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通