엄범


최악의 경우에도 선형 시간중간값을 선택할 수 있는 알고리즘은 다음과 같다.

* 다음은 median을 찾는 예이지만 일반적인 선택 문제에 적용 가능하다.


``c Element select(SetOfElements S, int k)``

1. 입력 배열이 n개라면 원소 5개짜리 \\(\lceil n/5 \rceil\\) 그룹으로 나눈다.

마지막 집합은 \\(n \mod 5\\)개 원소를 가질 수 있다.


2. 각 그룹에서 중앙값(`` _m``)을 찾는다. 중앙값을 찾는 데는 다음 방법을 사용한다.

2018/05/03 - [Algorithm/Theory] - 5개의 원소를 7번 비교로 정렬하기 / 6번 비교로 중간값 찾기


3. 이제 중앙값들의 중앙값(median of median, `` m``)을 찾아야 하는데, 어차피 이도 중앙값을 찾는 문제이므로 ``c select()``를 재귀적으로 호출한다. ``c m = select(M, M/2);`` 

* `` M``은 `` _m``들로 이루어진 집합(배열)을 의미한다.

* 이렇게 되면 개수가 짝수일 경우 `` m``은 더 앞에 있는 중앙값(`` M/2``)이 된다.

linear time selection algorithms에 대한 이미지 검색결과(`` x=m``)

4. x를 기준으로 x보다 큰 원소, x보다 작은 원소로 입력 배열을 분할한다.

x를 기준으로 좌측, 상단에 있는 모든 원소는 x보다 작은 원소들의 배열(`` S1``)로 넣는다.

x를 기준으로 우측, 하단에 있는 모든 원소(회색 영역)는 x보다 큰 원소들의 배열(`` S2``)로 넣는다.

나머지 영역에 대해서는 대소를 알 수 없으므로 x와 직접 비교해 알맞은 배열로 넣는다.


5. 분할 정복으로 해결한다.

```c

if (k == sizeof(S1) + 1)    // 여기서 k는 n/2. sizeof(S1) + 1은 m.

    return m;

else if (k <= sizeof(S1))

    return select(S1, k);

else

    return select(S2, k - (sizeof(S1) + 1));

```


수행 시간 분석

계산이 간단하도록 n이 5의 홀수 배라고 가정하면, 어떤 r에 대하여 \\(n = 5(2r + 1)\\)으로 정리할 수 있다.

1-2. 5개의 키 집합들에 대한 중앙값을 구하는 데는 5개의 원소의 중앙값을 찾는데 6번 비교하는 알고리즘을 사용했다고 가정하면 \\(6*(n/5)\\)번 비교.

3. 중앙값들의 중앙값을 찾는데 재귀를 사용하기 때문에 \\(W(n/5)\\)번 비교.

4. x를 기준으로 확실히 x보다 작은 원소와 큰 원소는 생각해보면 각각 \\(3r + 2\\)개라는 것을 알 수 있다. 따라서 대소를 알 수 없는 영역에 속하는 원소의 개수는 \\(n - (3r + 2) = 4r\\)개. 따라서 대소를 알 수 없는 영역에 속하는 원소와 \\(4r\\)번 비교.


5. 분할 정복법으로 ``c select()``를 재귀 호출 하는데, 최악의 경우는 대소를 알 수 없는 영역의 원소 전체가 x보다 작거나, 또는 x보다 큰 경우 이므로 \\(W(7r + 2)\\)번 비교. 


\\(r \approx n/10\\)이므로, \\(W(n) \le 1.6n + W(2n/10) + W(7n/10)\\)

점화식을 푸는데 재귀 트리를 이용해도 좋고(Computer Algorithms, Sara Baase)

수학적 귀납법을 이용해도 된다.(Introduction to algorithms)

재귀트리를 이용해 구해보면 \\(16n\\)이 나오는데, 최악의 경우 \\(2.95n\\)번 비교하는 알고리즘도 존재하기는 하나 꽤 복잡하다.

in-place는 아니지만 재귀의 깊이가 \\(O(\lg{n})\\)이므로 공간적인 부분이 많이 필요하지는 않다.


하한선

현재 최선의 하한선은 \\(2n\\) 정도로 알려져 있다.