algorithm - 广度优先搜索的时间和空间复杂度

Question

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

尤其是时间复杂度中的 b(b^d-1)

时间复杂度:完全 NumPy 。生成的节点数:1 + b + b2 + … + bd + b(b^d-1) = O(b^(d+1))空间复杂度:O(b^(d+1))

在哪里b – 搜索树的最大分支因子d – 最小成本解的深度

Answer 1

在根节点，您展开 b 节点作为搜索树中的下一个元素。如果这些都不是解决方案，则依次从每个节点扩展出 b 节点。这一直持续到找到解决方案，这将在深度 d。

因此:O(b^d)

(我不确定你从哪里得到 +1，但是...)