PRIM의 알고리즘 시간 복잡성은 우선 순위 Q를 사용하는 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 (log (v)) 및 O (log (e))는 동일합니다.
- e는 최대 v입니다2.
- 로그 (v2) = 2*로그 (V)
- O (log (v))
다른 팁
모든 가장자리 e (s, t) 사건에 대해
노드 수 s
최대를 가질 수 있습니까?
V-1
많으면. 따라서 PQ 운영에는 O (LOGV) 시간 복잡성이 있습니다.
제휴하지 않습니다 StackOverflow