作者mt1127 (馒头)
看板TransCSI
标题[问题] 图形执行时间
时间Tue Jun 24 09:10:01 2008
我都被搞混了..能不能请大大解释一下...
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