倒数第二题，问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