프림 알고리즘 코드의 시간복잡도에 관한 질문입니다.
O(VlogV) + O(ElogV) 의 시간복잡도를 갖는다고 하는데,
코드의 어떤 부분에서 위의 시간복잡도가 나오는 지 궁금합니다 !
답변해주시면 대단히 감사드리겠습니다 !!
네! 가중치, 정점번호 페어를 담고있는 이진힙입니다.
빠트려서 죄송합니다 ㅜㅜ
제 생각에는
1) 13-21 의 while 문에서 이진 힙에는 최대 V개의 edge 정보가 들어갈 수 있으며, 최악으로 마지막을 제외하고 모두 selected된 경우를 생각하면 O(VlogV)
2) 26-27 의 for 문에서는 최대 크기 V인 이진 힙에 정점 E개에 대해서 push를 하니까 O(ElogV)
라고 생각하는데 맞을까요?
가장 바깥은 9번 for 문은 사이클 체크를 위한 것이라고 생각이 들고요.
소스 코드는 다른 곳에서 참조하여 짜봤었습니다 ㅠㅠ..
(http://weeklyps.com/entry/%ED%...)
말씀 해주신 것처럼 while 안으로 넣고 한번에 처리 하는게 더 좋을 것 같습니다.
알려주셔서 감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
sjnov11 3년 전
프림 알고리즘 코드의 시간복잡도에 관한 질문입니다.
O(VlogV) + O(ElogV) 의 시간복잡도를 갖는다고 하는데,
코드의 어떤 부분에서 위의 시간복잡도가 나오는 지 궁금합니다 !
답변해주시면 대단히 감사드리겠습니다 !!