怎么古板的算法时的复杂性是ElogV使用的优先问?

Question

伪码我的使用：

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, 你能解释这是为什么？

Answer 1

O(日志(V))和O(日志(E))是相同的。

• E是在最V².
• 日志(V²)=2*日志(V)
• 这是一个O(日志(V))

Answer 2

对于所有的边缘e(s t)事件s

多边一点 s 可以在最？
V-1 在大多数。因此，PQ行动O(logV)时间的复杂性。