[理工] 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

繼續閱讀