关于这题下面回应
(3) 是 v^1.5
想问大家是怎么算的
谢谢！
※ 引述《mkchiun1028 (YO)》之铭言：
: 倒数第二题，问Prim's算法worst case的复杂度
: 点数V, 边数E=V^1.5
: (1) 没有使用任何data structure
: (2) 使用loser tree，leaf是cost最小的边
: (3) 使用Fibonacci Heap
: 大家这题写什么呢？

VlgV(extra-min)+E*O(1)(decrease-key)=O(V^1.5)想请问一下这题(1)的答案还有(2)得loser tree在这题里是怎么运作的?

1的答案好像很多种 我算是O(E + E + E ...+E) V-1次所以是O(VE) = O(V^2.5) (2)需要有人补充 看不懂@@ thx

2我认为 extractmin是跟一般heap一样动作花logV而decrease key则是从该data对应leaf往上调整花logV所以可以当作heap这样 整个time O(VlogV+VE)=(V^2.5)1的话我想到的有2种 O(V^2+E),O(V^3)两种

那我1应该是想错了。楼上能说说1的部分吗 感谢！

用一般array+adj list 循环+extract min 花V^2,DkeyO(1) 所以是O(V^2+E) 另一种是用matrix 每个vertex的for each v属于adj(u)这边要花O(V)*DkeyO (1)=O(V)所以total O(V^3)不过题目是写用list 所以我写第一种 但这样比(2)还XXXXXXXXXXX快...

谢谢各位 1说不能用其他资料结构，是不是也不能用array啊?不用array的话我一开始的想法可能跟yad大类似，一开始随便挑一个点V0，接着从V0的adjacency list中挑离V0最近的点，V1，再来从V0,V1的list中，挑离目前的树最近的点，V2，然后从V0,V1,V2的list中，再挑离目前树最近的点，依此类推每次都花O(E)，总共V次，所以是O(VE)不过我想说，每次选顶点时，应该要考虑这个点是不是已经在树里了，所以在扫描adjacency list里的每一个人时，都要花O(v)的时间，检查是不是已经在树里了，所以总共要花O(E*V^2)=O(V^3.5)的时间，不是很确定