我正在使用A*算法。我有一个二维网格，其中有一些障碍物，给定起始和终点位置，我会找到它们之间的最短路径。

这是我的伪代码

while(queueNotEmpty){  removeFromPQ;  if(removed == destination)    found;  insertAllNeighbours;}

移除和插入操作是在优先级队列（堆）上进行的，时间复杂度为O(log(n))。

考虑网格的维度为N*N。我如何计算运行时间？即这个循环会执行多少次？有什么衡量标准吗？

回答：

标准A*算法的运行时间在最坏情况下是解的长度的指数级别。

如果你在一个n*n的网格上进行搜索，并且使用图搜索，搜索将最多访问每个节点一次；因此时间复杂度为O(n*n)。但只有当使用的启发式函数是单调的（除了可接受之外），找到的解才是最优的。

标准A*算法的多项式运行时间也有条件。

关于图搜索与树搜索的区别，请参见这个回答。