倒數第二題，問Prim's演算法worst case的複雜度
點數V, 邊數E=V^1.5
(1) 沒有使用任何data structure
(2) 使用loser tree，leaf是cost最小的邊
(3) 使用Fibonacci Heap
大家這題寫什麼呢？
(1) V^3 (2) V^1.5logV (3) V^1.5
(1) O(V^2) (2) V^1.5logV (3) V^1.5
第一個 decress key 我是想成O(1) extract_min想成O(V)
第一個沒有提供data structure應該在adj list找?
我也是想adjacency list找 找min應該是O(V^1.5)?第一題我寫V^3.5 想說找min edge V^1.5, 比對有無cycle V^1, 重複做V次,總共V^3.5 只是很寬鬆就是了...
我是想第一個點找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