我的书（人工智能现代方法）说，统一成本搜索算法的最坏情况时间和空间复杂度将是 O(b[C/e])* ，其中b是分支因子，C *是最优解的成本，每个行动成本至少e . 但为什么会这样呢？
首先，复杂性是 O(B^(C/e)) [ C/e 中的指数] .
C/e
要理解它，首先想一个简单的示例案例：
设 G=(V,E) 为图形，分支因子为 B . 图表未加权（ w(e) = 1 为每个 e ） .
G=(V,E)
B
w(e) = 1
e
考虑找到从S到T的最短路径 .在这种情况下，算法实际上是 BFS ，它将发现路径中长度为 SOL 的所有节点，其中 SOL 是最短路径的长度，即 O(B^|SOL|)
SOL
O(B^|SOL|)
对于一般情况 - 同样的想法成立，您需要发现所有节点，最高成本为 C . 因此，您发现深度为 C/e 的节点，为您提供需要探索的总节点数 .
C
指数因子是因为：第一级（根）有 B^0=1 个节点，第二级有B节点 . 从这些中发现 B 节点，给你 B^2 ，....
B^0=1
B^2
EDIT:到目前为止错过了它，但 Headers 要求空间复杂性而不是时间复杂性 . 但是，答案保持不变，因为统一的成本搜索为已访问的节点保留了一个 visited 集 . 由于您发现的每个节点也被添加到它 - 答案仍然是 O(B^(C/e))
visited
O(B^(C/e))
C*/e 表示在搜索期间应访问的平均节点数，并且对于访问每个节点，您应该查看所有可能的 b 分支（至少是根节点），因此您应该检查您的b [C * / e]节点搜索 . 这是您的搜索时间复杂度，这是通过假设每个节点上的进程占用O（1） .
C*/e
b
P.S：在最坏的情况下，它是Ω（b [C * / e]）
2 回答
首先，复杂性是 O(B^(C/e)) [
C/e中的指数] .要理解它，首先想一个简单的示例案例：
设
G=(V,E)为图形，分支因子为B. 图表未加权（w(e) = 1为每个e） .考虑找到从S到T的最短路径 .
在这种情况下，算法实际上是 BFS ，它将发现路径中长度为
SOL的所有节点，其中SOL是最短路径的长度，即O(B^|SOL|)对于一般情况 - 同样的想法成立，您需要发现所有节点，最高成本为
C. 因此，您发现深度为C/e的节点，为您提供需要探索的总节点数 .指数因子是因为：第一级（根）有
B^0=1个节点，第二级有B节点 . 从这些中发现B节点，给你B^2，....EDIT:
到目前为止错过了它，但 Headers 要求空间复杂性而不是时间复杂性 . 但是，答案保持不变，因为统一的成本搜索为已访问的节点保留了一个
visited集 . 由于您发现的每个节点也被添加到它 - 答案仍然是O(B^(C/e))C*/e表示在搜索期间应访问的平均节点数，并且对于访问每个节点，您应该查看所有可能的b分支（至少是根节点），因此您应该检查您的b [C * / e]节点搜索 . 这是您的搜索时间复杂度，这是通过假设每个节点上的进程占用O（1） .P.S：在最坏的情况下，它是Ω（b [C * / e]）