stiti   4년 전

1. visited를 이용해서 방문한 노드를 체크하고

2. 체크된 노드들 중에서 가장 작은 값을 갖는 엣지를 연결하는

방식으로 해결하였습니다.

시간은 다른분들 코드보다 10배정도 더 걸리는 것 같은데요.
제 코드의 시간복잡도를 계산할 수가 없어서 질문드립니다.
제가 시간복잡도 이런걸 잘 모릅니다...ㅠㅠ

가장 바깥쪽의 while(1)이 vertex의 개수 -1 만큼 돌아가므로
V
while(!Q.empty())에서 Queue에 들어있는 Vertex들의 Edge를 조사하므로
한개의 Vertex에 연결된 Edge수의 평균은 E/V 이고 계산되는 Vertex의 평균은 V/2 이므로
(E/V) * (V/2) = E/2

V * (E/2)   =    세타(VE)
이런식으로 계산하면 되는건가요..?
알려주시면 감사드리겠습니다.

yunsubaek   4년 전

일단 cout을 printf로만 바꿔주시면 속도가 훨씬 빨라질것같네요!

baactree   4년 전

프림알고리즘에서 미니멈 엣지를 O(V)에 찾고 있어서 총 O((V+E)*V) 가 나오는 것 같아요 


다른 분들은 아마도 미니멈 엣지를 O(logE)에 찾을 수 있으므로 O((V+E)*logE) 에 풀었거나, 크루스칼 알고리즘을 사용하였을 것 같습니다  

stiti   4년 전

baactree님께서 말씀하면 V+E는 어디서 나오는 것인가요??

while(!Q.empty()) 부분이 V+E만큼 걸린다는 말씀이신가요?

찾고자 하는 Vertex각각에 연결된 Edge를 찾는 것인데 어떠한 방식으로 계산해서 V+E가 나오는 것인지 잘 모르겠습니다.

baactree   4년 전

밖의 while(1)은 V번 돌고 1번 정점에 다른 모든 정점이 연결 되어있다고 했을 때

첫 번째 for문 V번 돌고 그래프 탐색 포문도 E번 돌겠죠돌겠죠

stiti   4년 전

baactree

아 그렇군요 ㅎㅎ 정말 감사드립니다.

혹시 시간복잡도에 대해서 어떤 방식으로 공부하셨는지 여쭤봐도 될까요??

알고리즘 수업때 썻던 책을 다시 읽어보는게 가장 좋은 방법일까요?

baactree   4년 전

시간복잡도에 대해서 기본 개념만 알지 공부를 해본적은 없어서 잘 모르겠네요...

stiti   4년 전

네 정말 감사드립니다!

댓글을 작성하려면 로그인해야 합니다.