Time/Space 深度优先搜索的复杂度
Time/Space Complexity of Depth First Search
我看过其他各种 Whosebug 答案，它们都与我的讲师在他的幻灯片中写的不同。
Depth First Search has a time complexity of O(b^m), where b is the
maximum branching factor of the search tree and m is the maximum depth
of the state space. Terrible if m is much larger than d, but if search
tree is "bushy", may be much faster than Breadth First Search.
他接着说..
The space complexity is O(bm), i.e. space linear in length of action
sequence! Need only store a single path from the root to the leaf
node, along with remaining unexpanded sibling nodes for each node on
path.
Whosebug 上的 Another answer 指出它是 O(n + m)。
复杂度为 O(n + m)，其中 n 是树中的节点数，m 是边数。
老师之所以将复杂度表示为O(b ^ m)，可能是因为他想强调深度优先搜索和广度优先搜索之间的区别。
当使用 BFS 时，如果你的树的传播量与其深度相比非常大，并且你希望在叶子上找到结果，那么显然 DFS 在到达叶子时会更有意义比 BFS 更快，即使它们都在相同的时间（工作量）内到达最后一个节点。
当一棵树很深，并且非叶子可以提供有关更深节点的信息时，BFS 可以检测修剪搜索树的方法，以减少找到目标所需的节点数量。显然，你发现可以修剪子树的树越高，你可以跳过的节点就越多。
当您使用 DFS 时，这会更难，因为您优先考虑到达叶节点而不是探索更靠近根节点的节点。
时间复杂度：如果你可以在O(1)时间内访问每个节点，那么分支因子为b，最大深度为m，这个节点的总数树将是最坏的情况 = 1 + b + b2 + … + bm-1。使用对几何序列求和的公式（或什至我们自己求解）表明此总和 = (bm - 1)/(b - 1)，从而得出总访问时间每个节点与 bm 成正比。因此复杂度 = O(bm).
另一方面，如果您没有使用分支因子和最大深度，而是使用节点数 n，那么您可以直接说复杂度与n 或等于 O(n).
您在问题中链接的其他答案同样使用不同的术语。这个想法到处都是一样的。一些解决方案也加入了边数以使答案更精确，但一般来说，节点数足以描述复杂性。
Space复杂度：最长路径的长度=m。对于每个节点，您必须存储它的兄弟节点，这样当您访问了所有子节点并返回到父节点时，您可以知道接下来要探索哪个兄弟节点。对于路径中的 m 个节点，您必须为 m 个节点中的每一个额外存储 b 个节点。这就是你如何获得 O(bm) space 复杂度。
我想这个 DFS time/space 复杂性是在 AI class 上教授的，而不是在算法 class 上教授的。
这里的DFS搜索树含义略有不同：
A node is a bookkeeping data structure used to represent the search
tree. A state corresponds to a configuration of the world. ...
Furthermore, two different nodes can contain the same world state if
that state is generated via two different search paths.
引自书本'Artificial Intelligence - A Modern Approach'
所以这里的 time/space 复杂性集中在你访问节点并检查这是否是目标状态。 @displayName 已经解释的很清楚了
虽然O(m+n)在算法class中，重点是算法本身，当我们将图存储为邻接表时以及我们如何发现节点。
我看过其他各种 Whosebug 答案，它们都与我的讲师在他的幻灯片中写的不同。
Depth First Search has a time complexity of O(b^m), where b is the maximum branching factor of the search tree and m is the maximum depth of the state space. Terrible if m is much larger than d, but if search tree is "bushy", may be much faster than Breadth First Search.
他接着说..
Whosebug 上的The space complexity is O(bm), i.e. space linear in length of action sequence! Need only store a single path from the root to the leaf node, along with remaining unexpanded sibling nodes for each node on path.
Another answer 指出它是 O(n + m)。
复杂度为 O(n + m)，其中 n 是树中的节点数，m 是边数。
老师之所以将复杂度表示为O(b ^ m)，可能是因为他想强调深度优先搜索和广度优先搜索之间的区别。
当使用 BFS 时，如果你的树的传播量与其深度相比非常大，并且你希望在叶子上找到结果，那么显然 DFS 在到达叶子时会更有意义比 BFS 更快，即使它们都在相同的时间（工作量）内到达最后一个节点。
当一棵树很深，并且非叶子可以提供有关更深节点的信息时，BFS 可以检测修剪搜索树的方法，以减少找到目标所需的节点数量。显然，你发现可以修剪子树的树越高，你可以跳过的节点就越多。 当您使用 DFS 时，这会更难，因为您优先考虑到达叶节点而不是探索更靠近根节点的节点。
时间复杂度：如果你可以在O(1)时间内访问每个节点，那么分支因子为b，最大深度为m，这个节点的总数树将是最坏的情况 = 1 + b + b2 + … + bm-1。使用对几何序列求和的公式（或什至我们自己求解）表明此总和 = (bm - 1)/(b - 1)，从而得出总访问时间每个节点与 bm 成正比。因此复杂度 = O(bm).
另一方面，如果您没有使用分支因子和最大深度，而是使用节点数 n，那么您可以直接说复杂度与n 或等于 O(n).
您在问题中链接的其他答案同样使用不同的术语。这个想法到处都是一样的。一些解决方案也加入了边数以使答案更精确，但一般来说，节点数足以描述复杂性。
Space复杂度：最长路径的长度=m。对于每个节点，您必须存储它的兄弟节点，这样当您访问了所有子节点并返回到父节点时，您可以知道接下来要探索哪个兄弟节点。对于路径中的 m 个节点，您必须为 m 个节点中的每一个额外存储 b 个节点。这就是你如何获得 O(bm) space 复杂度。
我想这个 DFS time/space 复杂性是在 AI class 上教授的，而不是在算法 class 上教授的。
这里的DFS搜索树含义略有不同：
A node is a bookkeeping data structure used to represent the search tree. A state corresponds to a configuration of the world. ... Furthermore, two different nodes can contain the same world state if that state is generated via two different search paths.
引自书本'Artificial Intelligence - A Modern Approach'
所以这里的 time/space 复杂性集中在你访问节点并检查这是否是目标状态。 @displayName 已经解释的很清楚了
虽然O(m+n)在算法class中，重点是算法本身，当我们将图存储为邻接表时以及我们如何发现节点。