维基百科对 A* 的复杂性有以下说法：
A* 的时间复杂度取决于启发式。在最坏的情况下，扩展的节点数是解的长度（最短路径）的指数，但是当搜索空间是一棵树时它是多项式的......
我的问题是：“A* 的时间复杂度是指数级的吗？还是不是时间复杂度，而是内存复杂度？” 如果是内存复杂度，A*的时间复杂度是多少？
问问题
13153 次
3 回答
5
在最坏的情况下，A* 时间复杂度是指数级的。
但是，请考虑h(n) 估计的距离和h*(n)剩余的确切距离。如果条件| h(n) - h*(n) | < O(log *h(n) )成立，也就是说，如果我们的估计函数的误差呈次指数增长，那么 A* 时间复杂度将是多项式的。
可悲的是，大多数时候估计误差线性增长，因此，在实践中，更快的替代方案是首选，付出的代价是不再实现最优性。
于 2012-08-30T08:01:36.337 回答
3
由于存储每个扩展节点是为了避免多次访问同一节点，因此扩展节点数量的指数增长意味着指数时间和空间复杂度。
请注意，必要的指数空间复杂度意味着指数时间复杂度。反之则不成立。
于 2012-06-17T09:38:43.220 回答
0
A* 时间复杂度是指数的还是它的内存复杂度？
维基百科的摘录表明它指的是时间复杂度
于 2012-06-17T09:30:21.173 回答