Algorithm - 時間複雜度整理

以下資料摘自Ting的小筆記

###Sorting Algorithms 1362037892-2193125962.png

###Graph Algorithms | | Graph algorithm   | 時間複雜度 | strategy | negative weight | | —- | ———————— | ———— | ——– | ————— | | Ch22 | BFS(Breath-First Search) | O(V+E) | greedy | | | | DFS(Depth-First Search) | O(V+E) | greedy | | | Ch23 | Kruskal | O(E lgV) | greedy | allowed | | | Prim | O(E+V lgV) | greedy | allowed | | Ch24 | Bellman-Ford | O(VE) | DP | allowed | | | Dijkstra’s | O(E+V lgV) | greedy | not allowed | | Ch25 | Floyd-Warchall | O(V^3) | DP | allowed | | | Johnson’s | O(VE+V^2lgV) | gd + DP | allowed |

###參考資料 Ting的小筆記 - Algorithm time complexity 演算法時間複雜度整理 Sorting Introduction Sorting Comparison 小殘 - Bubble sort 排序(sorting)