广度优先和深度优先遍历树的时间和空间复杂度是什么？

Question

广度优先和深度优先遍历树的时间和空间复杂度是什么？

algorithm

101

能否举个例子解释一下如何计算这两种遍历方法的时间和空间复杂度？

此外，深度优先遍历的递归解法如何影响时间和空间复杂度？

- Frank Q.

2

维基百科上有相当不错的解释：http://en.wikipedia.org/wiki/Depth-first_searchhttp://en.wikipedia.org/wiki/Breadth-first_search - hc_

1

@hc_：维基百科的文章讨论了一般图，其中DFS必须维护“visited”集合。但是对于树来说这是不必要的。 - amit

好的问题参考：https://towardsdatascience.com/a-data-scientists-guide-to-data-structures-algorithms-part-2-6bc27066f3fe - David Peer

3个回答

47

DFS和BFS时间复杂度：O(n)

因为这是树的遍历，我们必须访问每个节点，使得时间复杂度为O(n)，其中n是树中节点的数量。

BFS空间复杂度：O(n)

BFS需要至少将一整层的树存储在队列中（参考队列实现）。对于一个完美的完全平衡二叉树来说，这将是（n/2 + 1）个节点（即最后一层）。在最佳情况下，即树严重不平衡并且每层只包含一个元素时，空间复杂度为O(1)。在最坏情况下，对于一个相当无用的N叉树，除了根节点外，所有节点都位于第二层，需要存储（n - 1）个节点。

DFS空间复杂度：O(d)

无论是使用递归还是迭代的方法，堆栈（隐式或显式）将包含d个节点，其中d是树的最大深度。对于平衡树来说，这将是（log n）个节点。DFS的最坏情况是BFS的最佳情况，而DFS的最佳情况则是BFS的最坏情况。

- Luke Heytens

11

应该是 O(V+E) 的时间复杂度，需要考虑边的数量。 - Kyle

6

@Kyle，在一般图的情况下你是对的。但在二叉树的情况下，时间复杂度为O(N)，因为边的数量是恒定的。 - Jiloc

6

如果你在寻找树木，这是最佳答案。 - SDG

4

所有的树（无论是否为二叉树）都有n-1条边。O（n + (n-1)）= O（n）。 - Luke Heytens

你确定非二叉树的DFS空间复杂度是O(d)吗？ - theonlygusti

这应该是正确的答案。问题明确要求关于树的内容。 - Jyhonn

7

复杂性有两个主要因素

时间复杂度
空间复杂度

时间复杂度

它是生成节点所需的时间量。

在DFS中，所需时间量与深度和分支因子成比例。对于DFS，所需总时间由以下公式给出 -

1 + b + b2 + b3 + ... + bd ~~ bd

因此时间复杂度 = O(bd)

空间复杂度

它是获取解决方案所需的空间或内存量，DFS仅存储其正在追求的当前路径。因此，空间复杂度是深度的线性函数。

因此空间复杂度为O(d)

- sumayla khan

这并不适用于树遍历，因为它是一种特殊情况。因此，这个答案可能会误导。 - xji

它应该是O(h)。因为d代表深度是相对于一个节点的。 - Fawkes

对于图遍历来说，时间复杂度为O（V+E）。当图稠密时，即所有节点互相连接时，最坏情况下时间复杂度是O（n^2）。 - Fawkes

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

BFS：

时间复杂度为O(|V|)，其中|V|是节点数量。您需要遍历所有节点。
空间复杂度也是O(|V|) - 因为在最坏的情况下，您需要在队列中保存所有顶点。

DFS：

时间复杂度同样为O(|V|)，您需要遍历所有节点。
空间复杂度-取决于实现方式，递归实现可能具有O(h)的空间复杂度[最坏情况]，其中h是树的最大深度。
使用堆栈的迭代解决方案实际上与BFS相同，只是使用堆栈而不是队列 - 因此您将获得O(|V|)时间和空间复杂度。

(*) 请注意，对于树，空间复杂度和时间复杂度与一般图稍有不同，因为您不需要为树维护一个visited集，而且|E|=O(|V|)，因此|E| 因素实际上是多余的。