search

ericdrowell / BigOCheatSheet

1.07k stars 314 forks source link

Update Tables.html #116

Open kanke opened 7 years ago

kanke commented 7 years ago

Searching Algorithms

Algorithm Time Complexity Space Complexity
Best Average Worst Worst
Depth First Search (DFS) N/A N/A O(|E| + |V|) O(|V|)
Breadth First Search (BFS) N/A N/A O(|E| + |V|) O(|V|)
Binary search N/A O(log(n)) O(log(n)) O(1)
Linear (Brute Force) N/A O(n) O(n) O(1)
Shortest path by Dijkstra,using a Min-heap as priority queue N/A O((|V| + |E|) log |V|) O((|V| + |E|) log |V|) O(|V|)
Shortest path by Dijkstra,using an unsorted array as priority queue N/A O(|V|^2) O(|V|^2) O(|V|)
Shortest path by Bellman-Ford N/A O(|V||E|) O(|V||E|) O(|V|)