9. Medians and Order Statistics

n개 원소들 중 i번째 순서 통계량은 i번째로 작은 원소이다. 최소값은 1번째 순서 통계량, 최대값은 n번째 순서 통계량, 하위 중위값\lfloor \frac{n+1}{2} \rfloor번째, 상위 중위값\lceil \frac{n+1}{2} \rceil 번째 순서 통계량이다. 중위값은 하위 중위값으로 정의하자. 이 때 다음의 선택 문제를 생각할 수 있다.

입력 : n개의 서로 다른 숫자들의 집합 A와 입력 1 \leq i \leq n.

출력 : A의 i번째 순서 통계량 x.

정렬해서 찾는 O(n \lg n)의 해법이 있지만 더 빠른 해법이 있다.

9.1. Minimum and maximum

최소값을 찾는 것은 쉽다. 선형 시간 안에 된다.

MINIMUM(A)
min = A[1]
for i = 2 to A.length
    if min > A[i]
        min = A[i]
return min

최대값도 마찬가지로 할 수 있다. 이것이 최선인가? 그렇다. 모든 원소를 한 번씩은 조사해야 하기 때문이다. 최대값과 최소값을 동시에 찾는 것은 어떻게 할까? 2n-2번 비교해야 하는가? 그렇지는 않다. 각각의 2개 원소 쌍마다 작은 것은 현재까지의 최소값과 비교하고 큰 것은 현재까지의 최대값과 비교하면 원소 2개당 3번의 비교를 하므로 3 \lfloor \frac{n}{2} \rfloor번 비교만으로 충분하다.

9.2. Selection in expected linear time

일반적인 선택 문제는 최소값/최대값 찾기보다 조금 더 어렵지만 역시 평균 \Theta(n) 시간에 가능하다. 이 때는 퀵 정렬과 비슷한 분할 정복 방법을 쓴다.

RANDOMIZED-SELECT(A, p, r, i)
if p == r
    return A[p]
q = RANDOMIZED-PARTITION(A, p, r)
k = q - p + 1
if i == k
    return A[q]
else if i < k
    return RANDOMIZED-SELECT(A, p, q - 1, i)
else
    return RANDOMIZED-SELECT(A, q + 1, r, i - k)

이 알고리즘의 최악의 수행 시간은 \Theta(n^{2})이다. 최소값을 찾을 때에도 분할 시마다 한 개의 원소만 분할된다면 각각의 분할은 \Theta(n)이기 때문이다. 하지만 평균 시간은 \Theta(n)이다.

랜덤 분할 이후의 왼쪽의 부분배열 A[p, \cdots, q]가 k개의 원소를 가진 사건에 대한 지시확률변수를 X_{k}라 하자. 랜덤 분할은 각각의 원소를 반환할 확률이 동일하므로 \mathbb{E}[X_{k}] = \frac{1}{n}이다. 이제 알아봐야 할 것은 랜덤 분할시에 분할 기준점이 i번째 원소가 되느냐 더 크냐 더 작냐의 문제인데, 문제는 수행 시간의 상한을 구하는 것이므로 일반성을 잃지 않고 i번쨰 원소는 항상 분할 중 더 큰 쪽에 존재한다고 가정하자. 그러면 T(n) \leq \sum_{k=1}^{n} X_{k} (T(\max(k-1, n-k)) + O(n)) = \sum_{k=1}^{n} X_{k} T(\max(k-1, n-k)) + O(n)이 된다.

기대값을 취하면, X_{k}T(\max(k-1, n-k))는 독립이므로

\mathbb{E}[T(n)] \leq \sum_{k=1} \mathbb{E}[X_{k} \cdot T (\max(k-1, n-k))] + O(n) = \sum_{k=1} \mathbb{E}[X_{k}] \cdot \mathbb{E}[T(\max(k-1, n-k))] + O(n) = \sum_{k=1}^{n} \frac{1}{n} \mathbb{E}[T(\max(k-1, n-k))] + O(n)이 된다.

\max(k-1, n-k)k > \lceil \frac{n}{2} \rceil일 때 k - 1, 아닐 때 n - k이므로 \mathbb{E}[T(n)] \leq \frac{2}{n} \sum_{k = \lceil \frac{n}{2} \rceil}^{n-1} \mathbb{E}[T(k)] + O(n)이 된다. 적당한 상수 c에 대해 \mathbb{E}[T(n)] \leq cn이라 하면

\mathbb{E}[T(n)] \leq \frac{2}{n} \sum_{k = \lceil \frac{n}{2} \rceil}^{n-1} ck + an = \frac{2c}{n}(\frac{(n-1)n}{2} - \frac{(\lceil \frac{n}{2} \rceil - 1)\lceil \frac{n}{2} \rceil}{2}) + an \leq \frac{2c}{n}(\frac{(n-1)n}{2} - \frac{ (\frac{n}{2} - 2)(\frac{n}{2} - 1)}{2}) + an = c(\frac{3n}{4} + \frac{1}{2} - \frac{2}{n}) + an \leq \frac{3cn}{4} + \frac{c}{2} + an = cn - (\frac{cn}{4} - \frac{c}{2} - an) 이 되는데, c > 4a, n < \frac{2c}{c - 4a}로 잡으면 뒤의 항은 O(1)이므로 \mathbb{E}[T(n)] = O(n)이 보장된다.

9.3. Selection in worst-case linear time

이제 위의 알고리즘을 개선시켜 최악의 수행 시간이 O(n)이 되도록 해 보자. SELECT 알고리즘은 다음의 스텝을 따른다.

  1. n개 원소의 배열을 \lfloor \frac{n}{5} \rfloor개의 5개짜리 원소 그룹과 n \mod 5개의 원소를 가진 그룹 0~1개로 나눈다.
  2. \lceil \frac{n}{5} \rceil 개 그룹의 중위값을 각각 삽입 정렬로 찾고, 각각의 그룹들에서 중위값들을 선택한다.
  3. SELECT 알고리즘을 이용해 \lceil \frac{n}{5} \rceil개의 중위값들 중의 중위값을 찾는다.
  4. 중위값 중의 중위값 x를 중심으로 원소들을 분할한다. x보다 작은 쪽의 원소의 수를 k – 1, x보다 큰 쪽의 원소의 수를 n – k라 한다.
  5. i = k면 x를 리턴한다. i < k면 x보다 작은 쪽에서 i번째 수를 SELECT하고, i > k면 x보다 큰 쪽에서 i – k번째 수를 SELECT한다.

이 알고리즘의 수행 시간은 어떻게 되는가? 중위값들 중 최소 절반 이상은 중위값의 중위값 이상이다. 그러므로 \lceil \frac{n}{5} \rceil 그룹 중 최소 절반 이상 그룹 중 최소 3개 이상의 원소는 (여기서 x를 포함한 그룹과 원소가 5개가 안되는 그룹 이렇게 2개는 제외된다) x보다 크다. 그러므로 x보다 큰 원소의 수는 최소 3(\lceil \frac{1}{2} \lceil \frac{n}{5} \rceil \rceil - 2) \geq \frac{3n}{10} - 6 개이다. 똑같이, 최소 \frac{3n}{10} - 6 개의 원소는 x보다 작다. 그러므로 최악의 경우에도 재귀 호출시에 대상이 되는 부분배열의 원소 수는 \frac{7n}{10} + 6개이다. 그러므로 수행 시간은 n < 140일 때 O(1)이고, n \geq 140일 때에는 T(n) \leq T(\lceil \frac{n}{5} \rceil) + T(\frac{7n}{10} + 6) + O(n)이 된다. 적당한 상수 c에 대해 T(n) \leq cn이라 하면 T(n) \leq c \lceil \frac{n}{5} \rceil + c(\frac{7n}{10} + 6) + an \leq c \frac{n}{5} + c(\frac{7n}{10} + 6) + an = \frac{9cn}{10} + 7c + an \leq cn이므로 (n > 140이기 때문에) T(n) = O(n)이다.

비교 모델로 선택 문제를 풀 때에는 O(n)이면 충분하다. 따라서 \Omega(n \lg n)이 드는 정렬로 문제를 푸는 것은 부적합하다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중