[理工] 104 台大资演 mkchiun1028 PTT批踢踢实业坊

楼主: mkchiun1028 (YO) 2015-02-09 21:12:35

倒数第二题，问Prim's算法worst case的复杂度
点数V, 边数E=V^1.5
(1) 没有使用任何data structure
(2) 使用loser tree，leaf是cost最小的边
(3) 使用Fibonacci Heap
大家这题写什么呢？

作者: galapous (墨) 2015-02-09 21:35:00

(1) V^3 (2) V^1.5logV (3) V^1.5

作者: harryron9 (两个世界) 2015-02-09 21:37:00

其实这题问的是worst case

作者: tp6m4xup6 (琳琳) 2015-02-09 21:42:00

(1) O(V^2) (2) V^1.5logV (3) V^1.5

作者: galapous (墨) 2015-02-09 21:43:00

worst没错吧!?

作者: tp6m4xup6 (琳琳) 2015-02-09 21:44:00

第一个 decress key 我是想成O(1) extract_min想成O(V)

作者: galapous (墨) 2015-02-09 21:46:00

第一个没有提供data structure应该在adj list找?

楼主: mkchiun1028 (YO) 2015-02-09 21:48:00

我也是想adjacency list找找min应该是O(V^1.5)?第一题我写V^3.5 想说找min edge V^1.5, 比对有无cycle V^1, 重复做V次,总共V^3.5 只是很宽松就是了...

作者: galapous (墨) 2015-02-09 22:01:00

我是想第一个点找min V 第二个点 2V 要做到V-1个点V+2V+...+(V-1)V=O(V^3)

作者: FRAXIS (喔喔) 2015-02-09 23:27:00

找 min 不能用 binary search吗?

作者: abc12321 (皓宇) 2015-02-09 23:42:00

题目说用greedy找

作者: APE36 (PT乡民) 2015-02-10 00:05:00

(2) 使用loser tree，leaf是cost最小请问为何是O(V^1.5log

继续阅读