[알고리즘] The Selection Problem - Median of Medians

K번째로 작은 값 찾기

Median of Medians

Quick sort으로 Selection 문제를 접근하는 데에 있어 불균형을 해결하기 위해서, 비교적 균등하게 배열을 나누는 알고리즘이다. 문제를 푸는 방법은 다음과 같다.

 

1. 배열 L을 5개씩 묶어준다. 즉, n/5로 분할한다.

2. 각 묶음에서 median 값을 찾는다. 이때, 묶음은 5개이므로 6번 비교하면 median 값을 찾을 수 있다. 비교 횟수는 총 (6 * n/5)번이다.

3. Median들 중에서 median인 m*을 찾는다. 이때 T(n/5)가 걸린다.

4. m*과 비교해서 loser 그룹과 winner 그룹으로 나눈다. 비교 횟수는 총 n번이다.

5. 재귀호출하거나 m*를 반환한다. 이때 T(|loser|) 이거나 T(|winner|) 시간이 걸린다.

따라서 MoM 알고리즘의 비교횟수 T(n) = 11n/5 + T(n/5) + T(3n/4)가 된다.

 

정리하면 다음과 같다.