作者future1234 (Creep)
看板TransCSI
标题Re: [问题] 图形执行时间
时间Mon Jun 30 20:45:17 2008
刚考完资料结构 ,来解一下 , 不过下面的今年都没出~
※ 引述《mt1127 (馒头)》之铭言：
: 我都被搞混了..能不能请大大解释一下...
: 1.下列哪个是有|V|个的顶点和|E|的边的topological sort problem 的执行时间?
: (A)O(V^2) (B)O(V+E) (C)O(ElogV) (D)O(V^3)
(B) O(V+E) ,每次删去In-dgree为0的点,并删去它的边,(共有V个点+E个边)的operations
: 2.下列哪个是有n个的顶点的All-pairs shortest paths algorithm 的执行时间?
: (A)O(n^2) (B)O(n^2logn) (C)O(n^3) (D)O(n^4)
(C) O(n^3)
: 3.有一个unicycle图有n个顶点,它有几个边?
: (A)n-1 (B)n (C)n+1 (D)n(n-1)/2
(B) n (不过这题我不太确定)
: 4.下列哪个是有|V|个的顶点和|E|的边的Bellman-Ford algorithm 的执行时间?
: (A)O(V^2) (B)O(V+E) (C)O(ElogV) (D)O(V^3)
O(VE) 这题有个选项应该是这个才对,这题的algo就要麻烦上网找了
: 5.下列哪个是有n个的矩阵的matrix-chain multiplication problem 的执行时间?
: (A)O(nlogn) (B)O(n^2) (C)O(n^2logn) (D)O(n^3)
(D) O(n^3) ,很明显低当p=q=r=n时(A matrix:pxq ,B matrix qxr) ,T(n)=O(n^3)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 203.67.210.63