The*_*e87 12 algorithm time-complexity depth-first-search space-complexity
我查看了其他各种StackOverflow答案,它们都与我的讲师在幻灯片中写的不同.
深度优先搜索的时间复杂度为O(b ^ m),其中b是搜索树的最大分支因子,m是状态空间的最大深度.如果m比d大得多,但是如果搜索树是"浓密的",则可能比广度优先搜索快得多.
他继续说..
空间复杂度为O(bm),即动作序列长度的空间线性!只需存储从根节点到叶节点的单个路径,以及路径上每个节点的剩余未扩展兄弟节点.
StackOverflow的另一个答案表明它是O(n + m).
dis*_*ame 17
时间复杂度:如果您可以在O(1)时间内访问每个节点,那么使用b的分支因子和m的最大深度,此树中的节点总数将为= b*b*b ... m次= b m,导致访问每个节点的总时间与b m成比例.因此复杂度= O(b m).
另一方面,如果不是使用分支因子和最大深度来获得节点数n,那么可以直接说复杂度将与n成比例或等于O(n).
您在问题中链接的其他答案同样使用不同的术语.这个想法无处不在.一些解决方案也增加了边缘计数以使答案更精确,但通常,节点数足以描述复杂性.
空间复杂度:最长路径的长度= m.对于每个节点,您必须存储其兄弟节点,以便当您访问所有子节点并返回父节点时,您可以知道接下来要探索的兄弟节点.对于路径下的m个节点,您必须为每个m个节点存储额外的b个节点.这就是你获得O(bm)空间复杂度的方法.
复杂度是树中节点的数量，O(n + m)是边的数量。 nm
你的老师之所以将复杂度表示为O(b ^ m)，可能是因为他想强调深度优先搜索和广度优先搜索之间的区别。
使用 BFS 时，如果您的树与其深度相比具有非常大的扩展量，并且您希望在叶子处找到结果，那么显然 DFS 在这里会更有意义，因为它比 BFS 更快到达叶子，甚至尽管它们都在相同的时间（工作）内到达最后一个节点。
当树非常深并且非叶子可以提供有关更深节点的信息时，BFS 可以检测修剪搜索树的方法，以减少找到目标所需的节点数量。显然，您发现可以修剪子树的树越高，您可以跳过的节点就越多。当您使用 DFS 时，这会更困难，因为您优先考虑到达叶子而不是探索更接近根的节点。