GESP 八级 · GESP 202412 C++ 八级 第 13 题

假设图 graph 中顶点数 $v$、边数 $e$，上题程序的时间复杂度为（ ）。

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

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

【考点】图存储结构（邻接矩阵）｜图遍历算法时间复杂度

考纲定位：本题考查图存储结构对算法复杂度的决定性影响，命题人故意用"图 graph"模糊表述，卡住考生对邻接矩阵与邻接表适用场景的区分——绝大多数人只会背"图算法 O(v+e)"，却忽略存储结构才是复杂度根源。

解题思维：看到"图"先判断存储结构——若为邻接矩阵，遍历所有顶点间边需 v×v 次访问，故时间复杂度必为 O(v²)；这是所有邻接矩阵下穷举边的算法共性，如求所有点对可达性、统计边数等。若用邻接表，复杂度才会降到 O(v+e)，所以本题核心是识别存储结构而非算法本身。

陷阱拆解：A 选项 O(e) 是邻接表遍历的复杂度，命题人用"图"一词误导考生默认邻接表；C、D 含对数项是堆优化 Dijkstra 的复杂度，与本题无关；最阴险的细节是题干未给出具体算法只给"上题程序"，考生若只背结论而不分析存储结构，必选错。

反命题思维：若把"邻接矩阵"改为"邻接表"，答案瞬间变 O(v+e)；若改用优先队列优化 Dijkstra，复杂度则成 O((v+e)log v)。刷到类似题先问"这题考的是存储结构还是具体算法？"