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

Question

我已经查看了其他各种StackOverflow答案，它们都与我的讲师在幻灯片中写的不同。

深度优先搜索的时间复杂度为O（b^m），其中b是搜索树的最大分支因子，m是状态空间的最大深度。如果m比d大得多，这很糟糕，但如果搜索树“浓密”，则可能比广度优先搜索快得多。

他接着说。。

空间复杂度为O（bm），即动作序列长度的空间线性！只需要存储从根到叶节点的单个路径，以及路径上每个节点的剩余未扩展兄弟节点。

StackOverflow上的另一个答案是O（n m）。

Answer 1

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

此处DFS搜索树的含义略有不同：

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

引自《人工智能——现代方法》一书

所以这里的时间/空间复杂度主要集中在你访问节点并检查这是否是目标状态。@displayName已经给出了非常明确的解释。

当O（mn）在算法类中时，重点是算法本身，当我们将图存储为邻接列表以及我们如何发现节点时。

Answer 2

复杂度为 O（n m），其中 n 是树中的节点数，m 是边数。

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

使用BFS时，如果你的树的深度有很大的传播量，并且你期望在叶子上找到结果，那么显然DFS在这里会更有意义，因为它比BFS更快地到达叶子，即使它们都在相同的时间（工作）内到达最后一个节点。

当一棵树很深时，非树叶可以给出关于更深节点的信息，BFS可以检测出修剪搜索树的方法，以减少找到目标所需的节点数量。显然，你发现你可以修剪的子树越高，你可以跳过的节点就越多。当您使用DFS时，这就更难了，因为您优先到达一个叶子，而不是探索更接近根的节点。

Answer 3

时间复杂度：如果您可以在O（1）时间内访问每个节点，那么在分支因子为b和最大深度为m的情况下，此树中的节点总数将是最坏情况=1 b b b＜sup＞2＜/sup＞b＜sup＜m-1＜/sup＞。使用对几何序列求和的公式（甚至自己求解）表明，这等于＝（b^m-1）/（b-1），导致访问每个节点的总时间与b^m成比例。因此复杂度=O（b^m）。

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

您在问题中链接的其他答案同样使用不同的术语。这个想法在任何地方都是一样的。一些解决方案也添加了边缘计数以使答案更精确，但一般来说，节点计数足以描述复杂性。

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