[알고리즘] 8. Approximate Median

1. Selection Strategy with Approximate Median

$a_1, a_2, ..., a_n$ 중에서 $[rn, (1-r)n]$ 등까지 있는 원소를 찾는다. 예를 들어 $r=0.3, n=100$인 경우 $[30, 70]$ 등 사이에 있는 것들을 Approximate Median 이라고 한다. Selection 문제는 n개의 원소에서 k등(정렬했을때 k번째) 원소를 찾는 것이다. 이때도 pivot을 이용하면 $O(n)$의 시간만에 구할 수 있다. Quick Sort에서 pivot을 기준으로 왼쪽 오른쪽으로 분류한 것과 같이 나눈 뒤 k등이 pivot 보다 왼쪽에 있으면 왼쪽 부분만 재귀적으로 Selection을 수행한다. k등이 pivot보다 오른쪽이면 오른쪽 부분만 재귀적으로 Selection을 수행한다. 이 과정을 반복하면 $O(n)$ 시간만에 k등 원소를 찾을 수 있다. 

• pivot이 중간값 (Median)인 경우: $T(n) = T(n/2)+n = ... = O(n)$
• pivot이 Approximate Median($r=0.3$) 인 경우: $T(n) = T(0.7n)+n = T(0.49n) + 0.7n + n = ... = O(n)$

 

2. Approximate Median과 Quick Sort

Quick Sort에서 $r=0.3$ 일때 Approximate Median 으로 피봇을 구해도 $O(nlogn)$ 의 시간이 걸린다. Worst Case에서 피봇은 Approximate Median의 가장 양 끝값인 경우가 될 것이다.

$\therefore T(n) = T(0.3n)+T(0.7n)+n = O(nlogn)$ 

Quick Sort에서 피봇을 선택하기 위하여 Selection 문제를 먼저 풀어야 한다. Selection 문제를 풀기 위하여 Approximate Median 알고리즘을 이용한다. 즉 pivot을 선택하기 위해 A.M 알고리즘을 돌리면 $O(n)$ 만에 선택할 수 있고, 이 경우 Quick Sort도 Worst Case에도 $O(nlogn)$ 만에 풀 수 있다. (하지만 이 경우 배열을 추가로 할당해야하는 문제점이 존재한다. 그래서 잘 쓰진 않음)

3. Approximate Median Algorithm

$r=0.3$일때 Approximate Median 을 찾는 알고리즘을 알아보자. 원소들을 5개씩 잘라서 하나의 그룹으로 만들고 그 그룹 내에서 정렬을 하면 $O(n)$ 시간안에 정렬이 된다. (아래에서 위 방향으로 커지게 정렬) 이제 각 그룹 내에서 중간값 (3등) 들끼리 모아서 Sorting 되었다고 가정하자. (실제로 정렬하진 않음, 나머지는 따라 움직인다고 생각) 3등들끼리 모은 배열에서 또 중간값을 Median X(초록색)라고 하자. 이 경우 배열 전체에서 0.3n개 (빨간색 그룹)는 항상 X보다 작고, 0.3n개(파란색 그룹) 는 항상 X보다 큼을 알 수 있다. 따라서 X는 Approximate Median이 된다.

 

4. 시간 복잡도

n개에서 A.M.을 푸려면 5개끼리 묶어서 그룹화를 하고($O(n)$), n/5개의 중간값들 중 Median을 찾아야 했다. 여기서 n/5개짜리 Selection을 해야 한다. (Selection을 하기 위해 A.M.을 쓰는데 그 안에 n/5개짜리 Selection이 있는 셈)
S를 Selection을 하는 시간, A를 A.M.을 하는 시간이라고 하자. $S(n)$ 은 n개짜리 Approximate Median 알고리즘을 돌림: $A(n)$ + 피봇 찾아서 왼쪽 오른쪽으로 구분: $O(n)$ + Selection을 다시 호출 (최대 Size: $S(0.7n)$)
A 안으로 또 들어가면 피봇 왼쪽 오른쪽으로 구분하는 $O(n)$ + n/5개짜리 Selection 시간 $S(0.2n)$ 

\[ \therefore S(n) = S(0.2n)+S(0.7n)+n, \ S(n) = O(n) \]
여기서 0.2와 0.7의 합이 1보다 작기 때문에 $O(n)$이 걸렸다. 만약 1이면 $O(nlogn)$의 시간이 걸렸을 것이다. 그래서 아까 1/5씩으로 끊은 것이다.