1回答

liuyubobobo

2018-06-06

已采纳

无论是在树结构中，还是图结构中，对于节点的遍历，无论是BFS，还是DFS，都是O(V+E)级别的。其中V是顶点个数；E是边数。这背后的直观理解也很简单，在遍历过程中，每个节点访问一次，每条边访问一次。

其中对于树，O(V+E) = O(V)，这是因为一个含有V个节点的树，有V-1条边，所以O(V+E) = O(2*V-1) = O(V)

对于图，稍微复杂一些。通常我们说O(V+E)，但是只有在稠密图的情况下，E才会和V产生显著的复杂度差别。在大多数情况下，处理的图都是稀疏图，此时可以近似的看做V和E在一个复杂度里，我们通常在不是特别严谨的场合，也可以说稀疏图的遍历也是O(V)级别的。因为每个节点肯定要访问一次。

这个问题的BFS是一个图模型，并且显然是一个稀疏图。（比如有100个节点的话，每个节点最多只会有10条边（10个完全平方数），远远小于99条边）所以，他的时间复杂度是O(n)的，n是数字个数。在我们的图模型中，每个数字是一个节点：）

0

1

benjaminfan

非常感谢！

2018-06-07

共1条回复