关于时间复杂度

来源：7-7 广度优先遍历和最短路径

小帆f

2023-07-04

稀疏图广度优先遍历，遍历了所有节点，为什么复杂度不是O(V)而是O(V+E)啊

写回答

1回答

liuyubobobo

2023-07-04

已采纳

因为你在遍历所有节点的时候，也尝试走了所有的边。

如果一个图有 100 个节点，3000 条边，如论是 DFS 还是 BFS，这 3000 条边都尝试走了，只不过有的尝试真的走到了一个新的节点，有的尝试没有。

你可以对应到程序里，找一找”尝试走边“的代码片段在哪里？

也可以试着测试一下，生成两个包含 5000 个节点的图，一个图有 4999 条边（整张图形成一个链）；一个图是完全图（包含 n * (n - 1) / 2）条边，然后实际测试一下，遍历这两张图的时间是否一致？（如果复杂度是 O(V) 的话，他们的性能应该近乎一致。）

继续加油！：）

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 2