분할정복 Divide & Conquer 알고리즘, 합병정렬 Merge Sort 이해하기

이번 글에서는 분할 정복 알고리즘에 대해 이해하기 위해 merge sort 복잡도를 분석해보겠습니다.

---

 Divide & Conquer Algorithm

분할 정복 알고리즘은 n개의 요소를 가진 문제를 n개의 부분 문제로 divide 하고 부분 문제들을 conquer하여 문제를 해결하는 방식입니다.

n개로 분할된 문제들을 해결하는 과정을 n번 반복해야 하므로 재귀적으로 해결할 수 있고, 이 과정에서 점화식을 활용할 수 있습니다. 

점화식이란

더 작은 입력에 대해 자신의 값으로 함수를 나타내는 방정식으로, 분할 정복 알고리즘에서 수행시간을 표현하는데 사용됩니다. 

 

• 예시 1)  T(n) = T(n-1) + Θ(1)
  • T(n) = 각 재귀 호출에 걸리는 시간은 상수시간 Θ(1) + 새로운 재귀 호출에 필요한 시간 T(n-1)이 필요하다. 

• 예시 2)  T(n) = a*T(n/b) + f(n)
  • 1/b 크기로 분할된 a개의 부분 문제의 분할 결합 과정이 f(n) 시간이 걸린다.

점화식을 푸는 방법으로는 치환법, 재귀트리방법, 마스터 방법이 있는데 이에 대한 설명은 추후에 새로운 글로 작성하도록 하겠습니다. 

---

합병 정렬 Merge Sort

merge sort에 관한 내용은 다음 글을 참고해주세요 :) 

합병 정렬은 n개의 요소를 가진 배열의 쪼개진 부분 배열에 요소 1개가 될 때까지 쪼개는 과정을 반복합니다. 그리고 쪼개진 부분 배열의 정렬을 하고(conquer) 부분적으로 정렬된 배열들을 다시 merge 하는 방식으로 정렬을 수행합니다. 

T(n) = T(divide) + T(conquer) + T(merge)

• T(divide) = Θ(1)

T(divide)는 문제를 분할하는데 걸리는 시간으로 merge sort에서 문제를 두개로 나눌 기준 인덱스 하나만 고르면 되기 때문에 O(1) 시간만이 걸리게 됩니다. 

즉, 문제를 1/b 크기의 부분 문제 a개로 분할한다고 가정합니다. 

• T(conquer) = 2*T(n/2)

T(conquer)는 분할한 부분 문제를 각 부분 문제를 푸는데 걸리는 시간을 곱한 시간을 의미합니다. n/2개의 요소를 가진 부분 문제가 2개가 생긴 것이기 때문에 T(n/2)*2 만큼의 시간이 걸립니다. 

즉, 크기가 n/b 인 부분 문제 a 개를 푸는데 a*T(n/b) 만큼의 시간이 걸리는 것입니다. 

• T(merge)=2*T(n/2)=Θ(n)

T(merge)는 결국 요소 개수만큼 merge를 수행하기 때문에 Θ(n) 만큼의 시간이 걸립니다. 

• Merge Sort의 시간 복잡도

결론적으로 merge sort의 시간 복잡도는 위 과정의 모든 시간을 더한 시간인 T(n) = Θ(1) + 2*T(n/2) + Θ(n) 입니다. 

 

---

References

• https://ratsgo.github.io/data structure&algorithm/2017/09/11/recurrence/