최소 스패닝 트리(MST)는 그래프에서 모든 정점을 가장 적은 비용으로 연결하는 트리를 의미합니다. 이러한 문제를 해결하는 알고리즘에는 여러 가지가 있지만, 대표적인 알고리즘인 Kruskal과 Prim 알고리즘이 있습니다. 이들 알고리즘의 시간 복잡도를 살펴보겠습니다.
Kruskal 알고리즘 시간 복잡도
Kruskal 알고리즘은 그리디 알고리즘의 일종으로, 간선들을 가중치 기준으로 오름차순으로 정렬한 뒤 가장 작은 간선부터 추가해 나가는 방식입니다. 이 알고리즘의 시간 복잡도는 크게 두 가지로 나눌 수 있습니다.
-
간선 정렬 시간 복잡도: 간선의 수에 따라 정렬하는 시간이 결정됩니다. 일반적으로 정렬 알고리즘에 의해 시간 복잡도는 O(ElogE)입니다. (E는 간선의 수)
-
간선 추가 및 유니온-파인드 연산 시간 복잡도: 모든 간선을 검사해야하므로 시간 복잡도는 O(E)입니다. 유니온-파인드 연산은 트리의 높이를 최소화하여 상수 시간에 실행할 수 있으므로 시간 복잡도는 상수입니다.
따라서, Kruskal 알고리즘의 총 시간 복잡도는 O(ElogE + E)로 정리할 수 있습니다.
Prim 알고리즘 시간 복잡도
Prim 알고리즘은 시작 정점에서부터 출발하여 연결된 정점 중에서 가장 작은 가중치를 갖는 간선을 선택해 나가는 방식입니다. 이 알고리즘의 시간 복잡도는 다음과 같습니다.
-
우선순위 큐를 사용한 정점 선택 시간 복잡도: 이진 힙을 이용한 우선순위 큐를 사용하는 경우, 정점의 수와 간선의 수에 비례하는 시간 복잡도를 가집니다. 일반적으로 시간 복잡도는 O((V+E)logV)입니다. (V는 정점의 수, E는 간선의 수)
-
인접한 정점의 갱신 시간 복잡도: 선택된 정점에 인접한 정점들을 검사하고 갱신하는 시간입니다. 이는 모든 간선을 검사해야하므로 시간 복잡도는 O(E)입니다.
따라서, Prim 알고리즘의 총 시간 복잡도는 O((V+E)logV + E)로 정리할 수 있습니다.
결론
최소 스패닝 트리(MST) 알고리즘인 Kruskal과 Prim의 시간 복잡도를 살펴보았습니다. 각 알고리즘은 간선의 수(E)와 정점의 수(V)에 따라 다른 시간 복잡도를 가지지만, 일반적으로는 Kruskal이 더욱 빠른 속도를 보입니다. 따라서, MST 문제를 해결해야 할 때는 Kruskal 알고리즘의 사용을 고려해볼 수 있습니다.
참고 자료
- Kruskal 알고리즘: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
- Prim 알고리즘: https://en.wikipedia.org/wiki/Prim%27s_algorithm