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

Question

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

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.

Another answer在 StackOverflow 上指出它是 O(n + m)。

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 个节点，您必须为 m 个节点中的每一个额外存储 b 个节点。这就是您获得 O(bm) 空间复杂度的方式。