时间和空间的广度优先搜索的复杂性 [英] time and space complexities of breadth first search

问题描述

我不明白是怎么下的复杂性来的。

i dont understand how the following complexities come from.

espeacialy为B（b ^ D-1）中的时间复杂度

espeacialy b(b^d-1) in the time complexity

时间复杂度： 总麻木。节点的产生： 1 + B + B2 + ... + BD +为B（b ^ D-1）= 0（二^（D + 1）） 空间复杂度：O（B ^（D + 1））

Time complexity: Total numb. of nodes generated: 1 + b + b2 + … + bd + b(b^d-1) = O(b^(d+1)) Space complexity:O(b^(d+1))

在哪里 b - 最大分支的搜索树的因素 ð - 成本最低的解决方案的深度

where b – maximum branching factor of the search tree d – depth of the least-cost solution

推荐答案

在根，展开了 B 节点作为搜索树的下一个元素。这些，如果没有一个是解决方案，进而扩大了 B 从每个节点。这样下去，直到找到解决办法，这将是在深度 D 。

At the root, you expand out b nodes as the next elements in the search tree. These, if none are the solution, in turn expand out b nodes from each. This continues until a solution is found, which will be at depth d.

因此​​：o（B ^ D）

Hence: O(b^d)

（我不知道，你得到了+1的，但是......）

(I'm not sure where you got the +1 from, however...)

这篇关于时间和空间的广度优先搜索的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！