글 읽기 - 프림 알고리즘과 코드의 시간복잡도

sjnov11 3년 전 0

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

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

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

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

priority_queue<pair<int, int>> dist; // <간선의 가중치, 정점번호> 이진힙
long long prim(int V){
    long long ret = 0;
    for(int i = 1; i <= V; i++){ 
        selected[i] = false;
    }
    dist.push(make_pair(0,1));	// 1번 정점부터 시작
    
    for(int i=1; i<=V; i++){	// V개의 정점을 모두 고른다
        int now = -1, min_dist = INF;
        // 간선의 가중치가 가장 작고,
        // 현재 MST에 포함되지 않은 정점을 찾는다.        
        while(!dist.empty()){
            now = dist.top().second;
            now_w = dist.top().first;
            dist.pop();
            if(!selected[now]){
                min_dist = now_w;                
                break;
            }
        }
        if(min_dist==INF) return (long long)INF;
        ret += min_dist;
        selected[now] = true;
        // 찾은 정점과 연결된 정점을 추가한다.
        for (auto next: adj_list[now]) {
            dist.push(next);
        }
    }
    return ret;
}

sjnov11 3년 전 0

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

빠트려서 죄송합니다 ㅜㅜ

sjnov11 3년 전 0

제 생각에는

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

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

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

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

sjnov11 3년 전 0

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

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

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

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

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

문제

문제

출처

ICPC

프림 알고리즘과 코드의 시간복잡도

sjnov11 3년 전 0

sjnov11 3년 전 0

sjnov11 3년 전 0

sjnov11 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말