我都被搞混了..能不能請大大解釋一下...
1.下列哪個是有|V|個的頂點和|E|的邊的topological sort problem 的執行時間?
(A)O(V^2) (B)O(V+E) (C)O(ElogV) (D)O(V^3)
2.下列哪個是有n個的頂點的All-pairs shortest paths algorithm 的執行時間?
(A)O(n^2) (B)O(n^2logn) (C)O(n^3) (D)O(n^4)
3.有一個unicycle圖有n個頂點,它有幾個邊?
(A)n-1 (B)n (C)n+1 (D)n(n-1)/2
4.下列哪個是有|V|個的頂點和|E|的邊的Bellman-Ford algorithm 的執行時間?
(A)O(V^2) (B)O(V+E) (C)O(ElogV) (D)O(V^3)
5.下列哪個是有n個的矩陣的matrix-chain multiplication problem 的執行時間?
(A)O(nlogn) (B)O(n^2) (C)O(n^2logn) (D)O(n^3)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.175.55.84