首页 文章

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

提问于
浏览
9

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

深度优先搜索的时间复杂度为O(b ^ m),其中b是搜索树的最大分支因子,m是状态空间的最大深度 . 如果m比d大得多,但是如果搜索树是“浓密的”,则可能比广度优先搜索快得多 .

他继续说..

空间复杂度为O(bm),即动作序列长度的空间线性!只需存储从根节点到叶节点的单个路径,以及路径上每个节点的剩余未展开的兄弟节点 .

StackOverflow上的Another answer表示它是O(n m) .

3 回答

  • 11

    复杂性为 O(n + m) ,其中 n 是树中的节点数, m 是边数 .

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

    当使用BFS时,如果你的树与其深度相比具有非常大的扩散量,并且你期望在叶子上找到结果,那么显然DFS在这里会更有意义,因为它比BFS更快到达叶子,甚至虽然它们都在相同的时间内(工作)到达最后一个节点 .

    当树非常深,而非叶子可以提供有关更深节点的信息时,BFS可以检测修剪搜索树的方法,以减少查找目标所需的节点数量 . 显然,您发现的树越高,您可以修剪子树,您可以跳过的节点越多 . 当您使用DFS时,这会更难,因为您优先考虑探索更接近根的节点 .

  • 1

    我想这个DFS时间/空间复杂性是在AI类上讲授的,而不是在Algorithm类上讲授的 .

    这里的DFS搜索树的含义略有不同:

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

    引自“人工智能 - 现代方法”一书

    因此,这里的时间/空间复杂性集中在您访问节点并检查这是否是目标状态 . @displayName已经给出了非常明确的解释 .

    当O(m n)在算法类中时,焦点是算法本身,当我们将图存储为邻接列表以及我们如何发现节点时 .

  • 1

    Time Complexity: 如果可以在O(1)时间内访问每个节点,那么分支因子为b,最大深度为m,此树中的节点总数将为= b * b * b ... m次= bm,从而导致访问每个节点的总时间与bm成比例 . 因此复杂度= O(bm) .

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

    您在问题中链接的其他SO答案同样使用不同的术语 . 这个想法无处不在 . 一些答案也增加了边数,以使答案更精确,但一般来说,节点数足以描述复杂性 .


    Space Complexity: 最长路径的长度= m . 对于每个节点,您必须存储其兄弟节点,以便在您完成访问所有子节点并返回父节点后,您可以知道接下来要探索的兄弟节点 . 对于路径下的m个节点,您必须为每个m个节点存储额外的b个节点 . 这就是你获得O(bm)空间复杂度的方法 .

相关问题