深度优先搜索的时间/空间复杂度

Question

我查看了其他一些StackOverflow答案，它们与我的讲师在他的幻灯片中写的不同。

深度优先搜索的时间复杂度为O(b^m)，其中b是搜索树的最大分支因子，m是状态空间的最大深度。如果m远大于d，则效率很低，但如果搜索树“多叉”，则可能比广度优先搜索快得多。

他接着说..

空间复杂度为O(bm)，即与操作序列的长度成正比！只需要存储从根到叶节点的单个路径，以及每个路径上所有未扩展兄弟节点的剩余部分。

StackOverflow上的另一个答案指出时间复杂度为O(n + m)。

- TheRapture87

---

深度优先搜索和广度优先搜索是泛指的术语，可以指涉很多算法，比如对树进行搜索或在游戏状态上做暴力搜索。 - eesiraed

Answer 1

时间复杂度：如果您可以在O(1)的时间内访问每个节点，那么在分支因子为b且最大深度为m的情况下，该树中的节点总数会达到最坏情况= 1+b+b²+…+b^m-1。使用求和等比数列的公式（甚至自己解决）告诉我们这总和= (b^m-1)/(b-1)，导致总访问每个节点的时间与b^m成比例。因此，复杂度= O(b^m)。

另一方面，如果您拥有节点数量n而不是使用分支因子和最大深度，则可以直接说复杂度与n成比例或等于O(n)。

您在问题中链接的其他答案也使用了不同的术语。所有地方的想法都相同。一些解决方案还添加了边缘计数以使答案更加精确，但通常，节点计数足以描述复杂度。

---

空间复杂度：最长路径的长度= m。对于每个节点，您必须存储其兄弟节点，以便当您访问所有子节点并返回父节点时，您可以知道要探索哪个兄弟节点。对于路径下的m个节点，您将不得不为每个节点存储额外的b个节点。这就是您获得O(bm)空间复杂度的方式。

- displayName

---

如果兄弟姐妹被存储在一个数组/链表中，你可以只保留数组索引/指向列表第一个元素的指针，这将使空间复杂度为O(m)。 - Witiko

@Witiko：完全正确。我应该在答案中写下这样一个巨大的改进是可能的。只是当提问者只想知道如何将复杂度变成O(bm)时，我没有那么想。 - displayName

Answer 2

复杂度为O(n + m)，其中n是您的树中节点数量，m是边的数量。

您的老师之所以将复杂度表示为O(b ^ m)，可能是因为他想强调深度优先搜索和广度优先搜索之间的区别。

使用BFS时，如果您的树的扩散量与其深度相比非常大，并且您希望在叶子节点找到结果，那么显然DFS在这里更加合适，因为它比BFS更快地到达叶子节点，尽管它们都在相同的时间（工作量）内到达最后一个节点。

当树非常深且非叶节点可以提供有关更深节点的信息时，BFS可以检测到如何修剪搜索树以减少查找目标所需的节点数。显然，您发现可以修剪子树的位置越高，跳过的节点就越多。 使用DFS时，这更加困难，因为您优先考虑到达叶子而不是探索更靠近根的节点。

- Glubus

Answer 3

我想这个DFS时间/空间复杂度是在人工智能课程上教授的，而不是算法课程。

这里的DFS搜索树有稍微不同的含义：

一个节点是一种用于表示搜索树的簿记数据结构。状态对应于世界的配置。此外，如果该状态通过两条不同的搜索路径生成，则两个不同的节点可以包含相同的世界状态。

引自书籍《人工智能-现代方法》

因此，这里的时间/空间复杂度集中在访问节点并检查是否为目标状态上。@displayName已经给出了非常清晰的解释。

虽然O(m+n)属于算法类，但重点是算法本身，我们如何将图存储为邻接列表以及如何发现节点。

- XueYu