时间复杂度必知

排序

算法	Time	Memory	特征
HeapSort	O(NlogN)	O(1)	Not Stable
MergeSort	O(NlogN)	O(N) reducible w/ in-place	Stable
QuickSort	O(NlogN) O(N²) worst case	O(logN) recursion stack	Not stable Applied for O(N) finding RANK
CountingSort	O(N)	-	Assumes known range
BucketSort	O(N)	-	Assumes ~Unif(range)

搜索

算法	树 b=branch factor m=tree depth	图 V=no. of vertices E=no. of edges
DFS	O(bᵐ)	O(V+E)
BFS	O(bᵈ), d=depth of solution	O(V+E)
Toposort	-	O(V+E)
Dijkstra	-	O((ElogV)
Bellman-Ford	-	O(V*E)
MST		O(ElogV)