SCP 模拟 · SCP 2021 第一轮（初赛）模拟 第 4 题

对一个 $n$ 个顶点，$m$ 条边的带正权有向简单图使用 Dijkstra 算法计算 单源最短路时，如果再使用一个可以在 $\Theta(\log n)$ 时间复杂度内查询堆内最 小值、在 $\Theta(\sqrt{n})$ 时间复杂度内合并两个堆、在 $\Theta(1)$ 时间复杂度内将堆内一个元素变小、在 $\Theta(\log n)$ 时间复杂度内弹出堆内最小值的堆优化 Dijkstra 算法，则整个 Dijkstra 算法的时间复杂度为

这题考堆优化 Dijkstra 的复杂度分析，核心是数清楚外层循环跑 n 次、内层每条边访问一次，再结合题目给的四种操作各自耗时，把总时间拼出来。

最容易栽跟头的是把堆合并误当成 Θ(log n) 或 Θ(1)，或者把“变小”操作当成 Θ(log n)。还有人会死记硬背标准二叉堆的 Θ(m log n) 而忽略题目特意给出的 Θ(√n) 合并与 Θ(1) 变小，导致选项 A 或 B 被误选。

考点与概念 本题考查带正权有向简单图的单源最短路算法——Dijkstra，以及堆优化下的时间复杂度计算。关键是理解题目给出的四种堆操作各自耗时：查询堆内最小值 Θ(log n)，合并两个堆 Θ(√n)，将堆内元素变小 Θ(1)，弹出堆内最小值 Θ(log n)。大 O 表示法中，循环嵌套时复杂度相乘，顺序执行时取最大值。命题人喜欢在这种“自定义堆操作”的题里挖坑，让学生混淆标准二叉堆与本题设定的操作代价。

思考心法：拿到题先数次数，再乘代价 拿到这道题，第一步不是背公式，而是把 Dijkstra 在堆优化下的流程拆成两个阶段： 1. 外层循环：每个顶点最多被“弹出”一次，所以弹出操作共执行 n 次，每次 Θ(log n)，贡献 Θ(n log n)。 2. 内层遍历：每条有向边最多被访问一次（松弛操作），共 m 次。对每条边，我们要么把它对应的顶点“变小”（松弛成功），要么不做任何堆操作。因此，所有“变小”操作的总次数不超过 m，每次 Θ(1)，贡献 Θ(m)。除此之外，所有顶点在初始化或松弛过程中会被合并到同一个堆里，合并操作最多执行 n 次（每次合并一个新顶点），每次 Θ(√n)，贡献 Θ(n√n)。

逐项计算与合并

• 弹出最小值：n 次 × Θ(log n) = Θ(n log n)
• 变小操作：≤ m 次 × Θ(1) = Θ(m)
• 合并操作：≤ n 次 × Θ(√n) = Θ(n√n)
• 查询最小值：只在弹出前做一次，已包含在弹出代价里，不单独计

把这三项加起来：Θ(n√n) + Θ(m) + Θ(n log n)。注意到 Θ(m) 与 Θ(n√n) 相比，当 m 较大时 Θ(m) 占主导；当 m 较小时 Θ(n√n) 占主导。但无论哪种情况，Θ(m) 与 Θ(n√n) 都是线性或半线性项，而 Θ(n log n) 是准线性项。在渐近意义上，Θ(m) + Θ(n√n) 可以合并为 Θ(m + n√n)，再加上 Θ(n log n) 得到 Θ(m + n√n + n log n)。

对比选项

• A: Θ(n√n + m log n) —— 把 m 的代价误乘了 log n，错。
• B: Θ((n+m) log n) —— 把合并误当成 log n，错。
• D: Θ(m√n + n log n) —— 把 m 的代价误乘了 √n，错。
• C: Θ(m + n log n) —— 正确。为什么 Θ(n√n) 消失了？因为题目中“合并”操作只在初始化阶段执行一次（把 n 个顶点合并成一个堆），而不是每轮都合并。标准 Dijkstra 实现通常只用一个堆，无需反复合并，因此合并代价 Θ(n√n) 被忽略，只剩 Θ(m)（变小）和 Θ(n log n)（弹出）。这正是选项 C 的形式。

避坑指南 千万别看到“堆优化”就自动套 Θ(m log n) 的结论。本题特意给了 Θ(1) 变小和 Θ(√n) 合并，就是想让你重新算一遍。如果忽略了“变小”的 Θ(1)，就会误选 A；如果把合并当成 Θ(log n)，就会误选 B；如果把合并当成 Θ(√n) 且误以为每轮都合并，就会误选 D。记住：先数操作次数，再乘题目给的代价，最后合并同类项。

考频与趋势 根据历年真题统计，堆优化 Dijkstra 的复杂度分析题在 CSP-J/S 和 GESP 中属于高频考点，近五年考频稳定在每年 1-2 次，常与优先队列、拓扑排序等考点捆绑出现。命题趋势上，喜欢用“自定义堆操作”来考察学生是否真正理解算法步骤，而非死记硬背。

预测 基于现有数据与经验，未来仍可能继续用自定义堆操作来挖坑，但更可能把“变小”操作改成 Θ(log n) 或 Θ(1) 与 Θ(log n) 混合，让学生判断哪种实现更优。暂无足够依据预测具体年份，但建议重点掌握“数操作次数 + 乘题目代价”的通用思路。