CSP-S 提高级 · CSP 2023 提高级第一轮 第 3 题

假设 $n$ 是图的顶点的个数，$m$ 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 $m=\Theta(n)$ 的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小（）。

这题核心就是代入 m=Θ(n) 后比谁增长慢。拿到题别急着套公式，先心算把 m 换成 n，看哪个选项里 n 前面的系数（那些对数项）最小。A 虽然看着复杂，但它的对数项乘积远小于 D 里的 log n，这才是解题关键。

最容易栽跟头的是把 A 当成 O(n) 直接秒杀，或者反过来觉得 D 的 O(n log n) 肯定比 A 大，却忽略了 A 里那个 √log n · log log n 其实比 log n 小得多。还有人会死磕 B 和 C，忘了题目是稀疏图，n² 级别的复杂度直接出局。另外，有些同学会把 log n 和 √log n 搞混，以为它们同阶，结果选错。记住，对数函数的增长速度差异巨大，√log n 和 log log n 在竞赛数据范围内几乎就是常数，但比 log n 慢一个数量级。

考察知识点：算法复杂度分析中的渐近比较，特别是稀疏图场景下不同算法的优劣对比。

命题视角：这道题是典型的“代入化简 + 对数级比较”。命题人故意给了四个看起来很复杂的式子，其中 A 选项带着 √log n 和 log log n，容易让学生产生“这玩意儿肯定比 log n 大”的错觉，或者干脆忽略这些缓慢增长项。但事实上，在稀疏图（m=Θ(n)）的前提下，这些项的乘积远小于 log n，这才是区分高手的关键。

代入化简：既然 m=Θ(n)，我们直接把 m 替换成 n 来看各选项的阶数：

• A: O(n√log n · log log n)
• B: O(n² + n) → O(n²)
• C: O(n²/log n + n log n) → 由于 n²/log n 占主导，整体是 O(n²/log n)
• D: O(n + n log n) → O(n log n)

比大小：现在问题简化为比较 n 前面的系数。

• B 是 n²，C 是 n²/log n，这两个都是平方级，直接排除。
• 剩下 A 和 D。D 是 n log n，A 是 n√log n · log log n。

这里有个关键技巧：比较 √log n · log log n 和 log n 的大小。我们知道 √log n 比 log n 小很多（比如 n=10^6 时，log n≈20，√log n≈4.5），log log n 更是小得可怜（约 4.3）。它们的乘积 ≈ 19，而 log n ≈ 20。也就是说，A 的系数实际上比 D 的系数还小！虽然 A 不是严格的 O(n)，但它的对数因子增长极慢，在渐近意义上它比 O(n log n) 小得多。

避坑提醒：千万别看到 A 里有两个对数项就以为它比 D 大，或者因为 A 不是纯 O(n) 就犹豫不决。在稀疏图场景下，A 就是最优解。另外，C 选项里的 n²/log n 虽然看起来比 n² 小，但还是平方级，远远甩不开 n² 的尾巴，所以只能排第二。

考频与趋势：根据题库数据，“循环结构”相关考点共考过 609 题。其中 CSP 提高级仅考了 5 题，但 2023 年这一题就是其中之一，说明这类复杂度比较题在提高级中并不罕见，且出题风格偏向于考察对对数级增长的敏感度。近年来（2022-2026）该考点考频显著上升，2023 年达 77 题，2024 年 128 题，2025 年 158 题，2026 年 161 题，呈爆发式增长，尤其在 GESP 高级别（四级、五级、六级）和 NOIP 提高组中频繁出现。

预测：基于数据趋势，未来 CSP 提高级和 GESP 六级、五级将继续高频考查算法复杂度分析，尤其是涉及稀疏图、对数级比较、以及非标准复杂度（如 n√log n）的选项设计。命题人可能会继续用类似的“看似复杂实则最优”的选项来挖坑，要求考生不仅会算，还要会“感觉”对数增长的速度差异。因此，熟练掌握各类对数函数的相对大小，是应对此类题目的必杀技。