Binary Search
最基本的二分查找法。the worst-case running time of binary search is Θ(logn). 因为你每次可以过滤掉总Array一半的elements,所以基本就是你总共可以把array size除2的次数。
A* Search
Uniform Search
表示Graph,一般都是用Adjacency List.
BFS
Overall Running time: O(|V|+|E|). 因为一共有2|V|次queue operations. 放进queue一次,pop出一次。然后对于每一个vertex,都会loop scan each edge 一次, 所以O(|E|).
Therefore, Overall Running time: O(|V|+|E|
DFS
每个Vertex都会去一次,每次到一个vertex,我们需要标记一下这个visited了. 一次标记是O(1). |V|次就是O(|V|).
然后每次在一个vertex标记完这里已经来过了以后, 扫描一下这个vertex的adjacent edges, 看看能不能去到一个新的node。【比如去到其child vertex】.
这一步总的runtime为O(|E|), 因为衣柜最多也就看|E| 个edges。所以DFS的总时间是O(|V|+|E|)
Dijkstra
Dijkstra 算法很像BFS,但是慢了一些因为用了PriorityQueue。由于Priority Queue有很多种不同的implementation,所以不同的implementation会导致不同的Run Time。