怎么古板的算法时的复杂性是ElogV使用的优先问?
-
19-09-2019 - |
题
伪码我的使用:
for all V vertices: visited[n]=0
pick any vertex r from graph and set visited[r]=1
For all edges e incident to r
PQ.insert()
while(PQ is not empty)//line 1
f=PQ.min()//f(r,s) is such that visited[s]=0
for all edges e(s,t) incident to s//line 2
if(visited[t]==0)
PQ.insert(e);//line 3
else
PQ.delete(e);//line 4
visited[s]=1;
end while;
根据我的理解:
- 第1行:执行
V-1
倍。 - 第2行总和程度的所有顶点。.就是
2E
时间
每个线2:线3和4行走 log E
时间因为我们增加或删除所有的边缘向/从 PQ
一个接一个。
所以总 time
= V-1+2E.logE
= E.log E
但是,这本书说这是 E.logV
, 你能解释这是为什么?
解决方案
O(日志(V))和O(日志(E))是相同的。
- E是在最V2.
- 日志(V2)=2*日志(V)
- 这是一个O(日志(V))
其他提示
对于所有的边缘e(s t)事件s
多边一点 s
可以在最?
V-1
在大多数。因此,PQ行动O(logV)时间的复杂性。
不隶属于 StackOverflow