Time and Space Complexity
Coddy의 프림 알고리즘 - 그래프 알고리즘 코스 레슨 — 9개 중 7번째.
시간 복잡도:
- 여기서의 간선 스캔 버전은 O(V * E)입니다: V-1번의 라운드 동안 매번 모든 E개의 간선을 스캔합니다. 이진 힙과 인접 리스트를 사용하면, Prim 알고리즘은 O((V + E) log V)의 시간 복잡도로 실행됩니다.
공간 복잡도:
inTree배열을 위해 O(V)가 필요합니다 (입력 간선 제외).
요약:
- Prim 알고리즘은 하나의 트리를 키워나가며, 모든 정점이 포함될 때까지 트리에서 나가는 가장 저렴한 간선을 계속 추가합니다.
- 이 알고리즘은 Kruskal과 다른 전략을 사용하지만, 동일한 최소 전체 가중치를 생성합니다.
직접 해보기
이 레슨에는 코드 챌린지가 없습니다.
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.
프림 알고리즘 - 그래프 알고리즘의 모든 레슨
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity