sjnov11   2년 전

프림 알고리즘 코드의 시간복잡도에 관한 질문입니다.

O(VlogV) + O(ElogV) 의 시간복잡도를 갖는다고 하는데, 

코드의 어떤 부분에서 위의 시간복잡도가 나오는 지 궁금합니다 !

답변해주시면 대단히 감사드리겠습니다 !!

sjnov11   2년 전

네! 가중치, 정점번호 페어를 담고있는 이진힙입니다.

빠트려서 죄송합니다 ㅜㅜ

sjnov11   2년 전

제 생각에는 

1) 13-21 의 while 문에서 이진 힙에는 최대 V개의 edge 정보가 들어갈 수 있으며, 최악으로 마지막을 제외하고 모두 selected된 경우를 생각하면 O(VlogV)

2) 26-27 의 for 문에서는  최대 크기 V인 이진 힙에 정점 E개에 대해서 push를 하니까 O(ElogV) 

라고 생각하는데 맞을까요? 

가장 바깥은 9번 for 문은 사이클 체크를 위한 것이라고 생각이 들고요.

sjnov11   2년 전

소스 코드는 다른 곳에서 참조하여 짜봤었습니다 ㅠㅠ..

(http://weeklyps.com/entry/%ED%...)

말씀 해주신 것처럼 while 안으로 넣고 한번에 처리 하는게 더 좋을 것 같습니다.

알려주셔서 감사합니다!!

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