[알고리즘] 탐욕법 - 프림 알고리즘과 크루스칼 알고리즘의 비교 (Greedy Approach - Comparing Prim's Algorithm with Kruskal's Algorithm)

앞서 보았듯이 시간 복잡도는 다음과 같습니다.

• Prim's Algorithm : \(T(n)\,\epsilon\,\theta(n^2)\)
• Kruskal's Algorithm : \(W(m, n)\,\epsilon\,\theta(mlgm) \, or \, \theta(n^2lgn)\)

 

또한 \(n-1 \leq m \leq \frac{n(n-1)}{2}\)이 성립합니다.

 

따라서 프림 알고리즘과 크루스칼의 알고리즘은 다음과 같은 상황에서 비교할 수 있습니다.

• For a Sparse Graph
  • edge의 개수인 m이 n-1과 가까운 희소 행렬의 경우에는
  • Kruskal's Algorithm is \(\theta(nlgn)\)이므로, Prim's Algorithm 보다 빠릅니다.
• For a Dense Graph
  • edge의 개수인 m이 범위의 상한에 가까운 밀접 행렬의 경우에는
  • Kruskal's Algorithm is \(\theta(n^2lgn)\)이므로, Prim's Algorithm 보다 느립니다.

 

감사합니다.

 

 

지적 환영합니다.