GESP 八级 · GESP 202403 C++ 八级 第 21 题

求一个包含 $v$ 个顶点、$e$ 条边的带权连通无向图的最小生成树，Prim 算法的时间复杂度为 $O(v \times e)$。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】Prim算法｜最小生成树｜时间复杂度分析

1. 🎯 考纲定位

本题考查GESP八级《数据结构与算法》模块中"生成树算法"的核心考点。命题人卡住的是考生对算法复杂度与实现方式强关联这一本质认知——八级考生容易把Prim算法的复杂度当成固定值，却忘了它取决于图的存储结构和实现细节。