BFS与DFS的时间及空间复杂度推导来源咨询

我们先统一参数定义：

• b：搜索树的分支因子，即每个节点的最大子节点数量
• d：BFS搜索场景下，目标解节点所在的深度
• m：DFS搜索场景下，搜索树的最大深度
  以下推导均基于「无环搜索树、每个节点仅被访问一次」的前置条件。

时间复杂度 O(b^d) #

BFS是逐层遍历的搜索策略，会按深度从小到大依次访问所有节点：

• 深度0（根节点层）共有 b^0 = 1 个节点
• 深度1共有 b^1 = b 个节点
• 深度2共有 b^2 个节点
• ...
• 深度d共有 b^d 个节点

最坏情况下，目标解是深度d层的最后一个被访问的节点，此时需要遍历完从深度0到深度d的所有节点，总节点数为等比数列求和：b^0 + b^1 + b^2 + ... + b^d = (b^(d+1) - 1)/(b-1)，当分支因子b>1时，最高次项为b^d，因此时间复杂度为O(b^d)。

空间复杂度 O(b^d) #

BFS采用队列存储待访问的节点，队列中同一时间最多保存的是当前层的所有节点。最坏情况下，当我们即将遍历深度d层的节点时，队列中会存储整个d层的所有b^d个节点，因此空间复杂度为O(b^d)。

时间复杂度 O(b^m) #

DFS是深度优先的搜索策略，会沿着一条分支走到最深节点后再回溯。最坏情况下，目标解不存在、或位于最深分支的最后一个位置，此时需要遍历完搜索树中所有深度不超过m的节点。总节点数等比数列求和后最高次项为b^m，因此时间复杂度为O(b^m)。

空间复杂度 #

DFS采用栈（递归栈或显式栈）存储当前搜索路径的节点状态，栈中始终只保留从根节点到当前访问节点的路径节点：

• 如果每个节点仅存储常数级的访问状态，最坏情况下路径长度等于搜索树的最大深度m，空间复杂度为O(m)
• 如果实现中需要为每个栈内节点存储所有b个待访问子节点的指针，每个节点的存储开销为O(b)，则总空间复杂度为O(b*m)，和部分资料的标注逻辑一致。

内容的提问来源于stack exchange，提问作者Mylisteofanime nexv