总结A*,Dijkstra,广度优先搜索,深度优先搜索的复杂度比较

时间:2021-09-25 03:41:56

广度优先搜索(BFS)

1、将头结点放入队列Q中

2、while Q!=空

u出队

    遍历u的邻接表中的每个节点v

    将v插入队列中

当使用无向图的邻接表时,复杂度为O(V^2)

当使用有向图的邻接表时,因为每条边只访问一次,不会重复访问,所以总复杂度为O(V+E)

深度优先搜索(DFS)

for each vertex u∈V(G)    //执行时间为O(V)

  DFS(u)

DFS内部:

for each v 为u的邻接点      //执行时间为O(E)

  DFS(v)

总执行时间为O(V+E)

A*搜索

从A开始,遍历周围的点,且避开close中以及障碍点,利用f(x) = g(x)+h(x)评价这些点,选取最佳点。并且如果第二次评价某点时,取记录中该点的f(x)值与现在计算得到的f(x)值更小的,放入到记录中

算法复杂度:

外循环中每次从open中取出点,共取n次,

内循环:遍历它的邻接点n(E),并将这些邻接点放入open中,对open进行排序,open表大小是O(n)量级的,若用快排就是O(nlogn),内循环总的复杂度为O(n*logn+E)=O(n*logn)

总复杂度为 O(n^2*logn)

Dijkstra(旅行商问题,最短距离遍历所有的城市)

总结A*,Dijkstra,广度优先搜索,深度优先搜索的复杂度比较
总结A*,Dijkstra,广度优先搜索,深度优先搜索的复杂度比较
行2--4的初始化对n个顶点进行,显然是O(n)
5--6行O(1)
7行n个顶点入队列O(n)
8行--14行,从8行可以看出进行了n遍循环,每遍在第九行调用一次ExtractMin过程,ExtractMin过程需要搜寻邻接表,每一次需要搜寻整个数组,所以一次操作时间是O(n);11行到14行对节点u的邻接表中的边进行检查,总共有|E|次(总共.每条边最多检查一次),因此是O(E);合起来就是O(E+n*n) = O(n^2); 以上合起来就是O(n)+O(1)+O(n)+O(n^2) == O(n^2)

算法复杂度:

O(V^2)