维基百科关于A *复杂性的解释如下：
引用：
引用：
A*的时间复杂度取决于启发式算法。在最坏情况下，展开的节点数与解（最短路径）的长度呈指数关系，但当搜索空间是树时，它是多项式的...
我的问题是：“A *的时间复杂度是否为指数级？还是说它不是时间复杂度，而是内存复杂度？如果是内存复杂度，那么A *的时间复杂度是什么？”A*时间复杂度
7
- Szkandy
2
2它说时间复杂度。 - leppie
可能是重复问题：https://dev59.com/U3I-5IYBdhLWcg3wta1q - Dima Chubarov
3个回答
5
在最坏的情况下，A*算法的时间复杂度是指数级的。但是，如果满足条件
| h(n) - h*(n) | < O(log *h(n) )，其中h(n)是估计距离，h*(n)是剩余的精确距离，也就是说，如果我们的估计函数的误差呈现亚指数增长，那么A*算法的时间复杂度将是多项式级别的。不幸的是，大部分情况下，估计误差是线性增长的，因此在实际应用中，更快的替代方案更受欢迎，但这也意味着不能保证最优解。- coredump
3
由于每个扩展节点都被存储以避免多次访问同一节点，所以扩展节点数量的指数级增长意味着指数时间和空间复杂度。
请注意，指数空间复杂度必然意味着指数时间复杂度。反之则不成立。
- Dmitri Chubarov
2
4很抱歉，这并不是完整的答案。因为维基百科上的文章说A*算法在解的长度方面是指数级别的。这与复杂度理论的标准设置不同，后者是根据输入的长度来衡量复杂度的。 - Dima Chubarov
2它的时间复杂度是
O((|V| + |E|) log |V|)。用图的大小来描述A*算法复杂度是最有意义的。这个答案令人惊讶地差劲（也许是受维基百科影响？肯定不是Cormen...）。 - PawelP0
"A*算法的时间复杂度是指数级还是内存复杂度？"，这个维基百科的摘录表明它是指时间复杂度。
- James Webster
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接