[Algorithm] 분할정복(5) - Median of Medians

🤔분할정복

분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다.

 

이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다.

 

이번 포스팅에서는 Median of Medians 에 대해 알아보겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Median Of Medians

크기가 $n$인 배열 A가 주어졌을 때 A에서 k번째 작은 원소를 찾는 알고리즘을 찾아보겠습니다.

 

앞선 Quicksellect의 시간복잡도 분석에서 결국 Quickselect의 성능은 '좋은 pivot을 얼마나 빠르게 찾아내는가'에 달려있다는 것을 알 수 있었습니다.

 

좋은 pivot을 찾기 위한 효율적인 알고리즘이 있다면 성능이 좋아진다는 것이고 그 방법 중 하나가 Median Of Medians입니다.

 

 

 

Step 0: 먼저 Base Case로 'A의 크기가 25이하이면 그냥 A를 sorting하여 문제를 해결한다'라고 합니다.

 

 

 

Step 1: 이후 A의 크기가 25 이상이면 A를 크기가 5인 $n/5$개의 subarray 들로 나눕니다.

 

 

 

 

 

Step 2: 각 subarray의 median 즉 3번째로 작은 element를 찾은 이후 이들을 배열 M에 저장합니다.

 

이때 중요한 것은 subarray에서 median값을 찾기 위해서 어떤 알고리즘을 사용해도 무방하다는 것입니다.

 

왜냐하면 크기가 5인 배열에서 median값을 찾는 데에는 어떤 방법을 사용하더라도 크기가 상수여서 $O(1)$의 시간이 걸리기 때문입니다.

 

참고로 최적의 방법을 통해 median값을 찾기 위해서는 6번의 비교만 진행하면 됩니다.

 

 

 

Step 3: M의 median을 quickselect using median of medians로 찾아내고 이를 pivot으로 둡니다.

 

이때 median of medians는 A[1] A[8] ... A[43] 중 어떤 값이 선택되어도 무방합니다.

 

그 다음은 앞선 quick select와 마찬가지로 진행하면 됩니다.

 

M을 푸는 것을 일종의 subproblem이라고 생각하고 풀면 됩니다.

 

 

이를 수도코드로 나타내면 아래와 같습니다.

 

 

 

이때 $m$이 subarray 개수가 되며  $MedianOfFive(A[5i - 4 .. 5i])$를 통해 5개중 3번째로 작은 숫자를 $M[i]$에 저장합니다.

 

배열 M에 모아둔 pivot들을 MomSelect라는 함수를 통해 재귀적인 방법으로 mom(median of medians)에 저장합니다. 

 

이후 partitioning 한 이후 A1 혹은 A2로 가서 subproblem을 해결하면 됩니다.

 

즉 평균적으로 총 두 번의 subproblem을 해결해야 합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Median Of Medians는 얼마나 좋은 pivot인가?

 

 

 

 

 

 

위의 예시와 같이 각각의 subarray가 위에서 아래 순서대로 정렬되어있고 노란색 부분또한 왼쪽에서 오른쪽으로 정렬되어 있다고 하겠습니다.

 

이때 파란색 부분이 mom이 됩니다.

 

이때 주의할 점은 첫 번째 subarray의 노란색 아래에 있는 요소가 큰 지 다음 subarray들의 노란색 위에 있는 요소가 큰 지는 알 수 없다는 것입니다.

 

즉, 아래의 그림과 같이 빨간색 박스 안에 해당하는 요소들은 mom보다 무조건 작거나 같다는 것을 알 수 있습니다.

 

 

 

 

 

 

전체 element의 수가 $n$이라고 했을 때 mom은 적어도 $\frac{3n}{10}$개의 요소보다는 무조건 큽니다.

 

 

 

 

마찬가지로 아래의 그림에서 빨간 박스 안에 해당하는 부분은 mom보다 무조건 크거나 같습니다.

 

그러므로 mom은 적어도 $\frac{3n}{10}$개의 요소보다는 무조건 작습니다.

 

 

 

 

따라서 mom을 피봇으로 했을 때 partitioning하는 경우 해당 부분을 제외한 부분의 subproblem만을 해결하면 되기 때문에  해결해야하는 subprooblem의 크기는 최대 $\frac{7n}{10}$입니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Median Of Medians의 시간복잡도

$T(n)$을 크기가 $n$인 배열에서 quickselect with median of medians를 하는데 걸리는 worst-case time이라고 하겠습니다.

 

$T(n)$은 배열 M에서 median을 찾는 시간 +  partitioning 후 subproblem을 해결하는 시간 + $n/5$개의 배열을 정렬하는 시간($n/5 * O(1) + partitioning)이므로 아래와 같은 식으로 나타낼 수 있습니다.

 

$$T(n) = T(n/5) + T(7n/10) + O(n)$$

 

위의 식은 recurrence relation에 따라 특정 level의 노드에 해당하는 subproblem 들의 input size의 총 합은 이전 level의 노드에 해당하는 subproblem의 input size와 비교하여 $9/10$배 이상이 되지 않습니다.

 

즉, 아래와 같이 나타낼 수 있습니다.

 

$$T(n) ≤ T(7n/10) + O(n)$$

 

Master Theorem에 의해 $T(n) = O(n)$이 됩니다.