常用算法和数据结构的复杂度速查表，
搜索
算法数据结构时间复杂度空间复杂度
平均最差最差
深度优先搜索 (DFS)
Graph of |V| vertices and |E| edges
-
O(|E| + |V|)
O(|V|)
广度优先搜索 (BFS)
Graph of |V| vertices and |E| edges
-
O(|E| + |V|)
O(|V|)
二分查找
Sorted array of n elements
O(log(n))
O(log(n))
O(1)
穷举查找
Array
O(n)
O(n)
O(1)
最短路径-Dijkstra，用小根堆作为优先队列
Graph with |V| vertices and |E| edges
O((|V| + |E|) log |V|)
O((|V| + |E|) log |V|)
O(|V|)
最短路径-Dijkstra，用无序数组作为优先队列
Graph with |V| vertices and |E| edges
O(|V|^2)
O(|V|^2)
O(|V|)
最短路径-Bellman-Ford
Graph with |V| vertices and |E| edges
O(|V||E|)
O(|V||E|)
O(|V|)