BFS 和 DFS 复杂度
BFS and DFS complexity
我不明白 BFS 和 DFS 的这些复杂性
对于 BFS，时间复杂度为（d 是树中解节点的深度，b 是节点子的最大数量）
space 复杂度被写为
对于 DFS 时间复杂度是（m 是树的最大深度）
它的space复杂度是
谁能解释一下这些是从哪里来的
对于 BFS，每次迭代都在探索一个节点队列，构建下一个队列并递归到其中。
def bfs(startNode, target):
queue = [startNode]
while len(queue) > 0:
next_queue = []
for node in queue:
if node == target: return True
next_queue.append(node.children)
queue = next_queue
return False
一开始，队列只有一个元素，但是因为队列中的每个节点都将其所有子节点添加到下一个队列中，并且因为每个节点最多可以有b个子节点，所以队列的大小可以增长每次迭代乘以 b 倍。您可能在第一次迭代中在队列中有 1 个节点，然后在第二个循环中最多有 b 个节点，这些 b 个节点中的每一个可以自己将 b 个节点添加到第三个队列，产生 b*b = b^2 个节点，然后是 b^3节点下一个循环，依此类推。这可以继续进行，直到目标节点到达深度 d，此时队列中最多可以有 b^d 个节点。因为队列保存在内存中，所以这会花费 O(b^d) space，并且因为队列中的每个节点在循环的每次迭代（大概）恒定时间内处理，时间复杂度与您一样表示 O(1 + b + b^2... + b^d) = O(b^{d+1})。 （请注意，如果目标不在图中，这仍然是 O(b^m)。）
关于 dfs：
def dfs(node, target):
if node == target: return True
found = false
for child of node.children:
found = dfs(child, target)
if found: break
return found
对于dfs，不能保证你的搜索走正确的分支直达目标节点。您尽可能深入，递归地探索每个节点的第一个子节点，直到搜索触底，然后再分支到一边。因此，您可以搜索比目标节点的深度 d 更深的深度，并且在最坏的情况下，可以探索到最大深度并在找到目标之前处理整个图。由于Graph最多可以包含b^m个节点，dfs的时间复杂度是O(b^m)。要分析 space 的复杂性，请注意，在搜索触底之前，您最多可以进行 m 次递归调用。进行函数调用需要 space：深度为 m 的调用堆栈至少需要 O(m) space。但是，给定节点上的每个递归调用都会引用该节点的所有子节点，最多 b 个，需要 O(b) space。这意味着调用堆栈上的每个调用都需要 O(b) space，并且由于最多有 m 个这样的调用，因此 dfs 总共需要 O(bm) space。
我不明白 BFS 和 DFS 的这些复杂性 对于 BFS，时间复杂度为（d 是树中解节点的深度，b 是节点子的最大数量）
space 复杂度被写为
对于 DFS 时间复杂度是（m 是树的最大深度）
它的space复杂度是
谁能解释一下这些是从哪里来的
对于 BFS，每次迭代都在探索一个节点队列，构建下一个队列并递归到其中。
def bfs(startNode, target):
queue = [startNode]
while len(queue) > 0:
next_queue = []
for node in queue:
if node == target: return True
next_queue.append(node.children)
queue = next_queue
return False
一开始，队列只有一个元素，但是因为队列中的每个节点都将其所有子节点添加到下一个队列中，并且因为每个节点最多可以有b个子节点，所以队列的大小可以增长每次迭代乘以 b 倍。您可能在第一次迭代中在队列中有 1 个节点，然后在第二个循环中最多有 b 个节点，这些 b 个节点中的每一个可以自己将 b 个节点添加到第三个队列，产生 b*b = b^2 个节点，然后是 b^3节点下一个循环，依此类推。这可以继续进行，直到目标节点到达深度 d，此时队列中最多可以有 b^d 个节点。因为队列保存在内存中，所以这会花费 O(b^d) space，并且因为队列中的每个节点在循环的每次迭代（大概）恒定时间内处理，时间复杂度与您一样表示 O(1 + b + b^2... + b^d) = O(b^{d+1})。 （请注意，如果目标不在图中，这仍然是 O(b^m)。）
关于 dfs：
def dfs(node, target):
if node == target: return True
found = false
for child of node.children:
found = dfs(child, target)
if found: break
return found
对于dfs，不能保证你的搜索走正确的分支直达目标节点。您尽可能深入，递归地探索每个节点的第一个子节点，直到搜索触底，然后再分支到一边。因此，您可以搜索比目标节点的深度 d 更深的深度，并且在最坏的情况下，可以探索到最大深度并在找到目标之前处理整个图。由于Graph最多可以包含b^m个节点，dfs的时间复杂度是O(b^m)。要分析 space 的复杂性，请注意，在搜索触底之前，您最多可以进行 m 次递归调用。进行函数调用需要 space：深度为 m 的调用堆栈至少需要 O(m) space。但是，给定节点上的每个递归调用都会引用该节点的所有子节点，最多 b 个，需要 O(b) space。这意味着调用堆栈上的每个调用都需要 O(b) space，并且由于最多有 m 个这样的调用，因此 dfs 总共需要 O(bm) space。