9. Selection(Order Statistics)

The k th element selection

n개의 숫자로 이루어진 배열에서 $k^{th}$ element를 찾는 문제입니다. 가장 쉽게 생각해보면, 배열을 정렬해서 $k^{th}$ element를 얻으면 될 것 같습니다. 보통 정렬이 $O(nlogn)$이 소요되는 데, 이보다 빠르게 linear time에 이를 수행할 수 없을까요?

 

Randomized algorithm

가장 먼저 Divide-and-conquer 방법을 생각해 볼 수 있습니다. 다음의 방법을 생각해 봅시다.

1. $i^{th}$ element를 pivot으로 정합니다.
2. pivot을 기준으로 작은 값은 앞으로, 큰 값은 뒤로 옮깁니다.
3. pivot은 배열에서 자기의 자리를 찾게 됩니다.
4. 이렇게 해서 원하는 $k^{th}$ element를 찾습니다.

 

Best case: $O(1)$

Worst case: $O(n^2)$

 

목표는 linear time을 보장하는 것인데 worst case에 $O(n^2)$의 시간 복잡도가 소모됩니다. Worst case의 시간 복잡도를 해결하는 방법으로 좋은 방법이 있습니다. 바로 Randomization입니다.

 

Finding $k^{th}$ element

증명 과정은 다음과 같습니다.

이를 통해 Linear time에 $k^{th}$ element를 찾는 것이 가능함을 알 수 있습니다.

 

Worst-case guaranteed algorithm

하지만 randomization을 사용하기 때문에 여전히 worst case에 $O(n^2)$의 시간 복잡도가 소모되게 됩니다. Worst case에 대해서도 linear time selection이 가능할까요?

 

Selection using midian of medians

위와 같은 알고리즘을 생각해 봅시다. 각 배열을 같은 길이로 나누고 그룹의 중간값을 비교해 $k^{th}$ element를 찾는 방법입니다. 구체적인 알고리즘은 다음과 같습니다.

 

Median of medians

그리고 알고리즘의 시간 복잡도 증명 과정은 다음과 같습니다.

이렇게 해서 worst case에도 linear time에 $k^{th}$ element를 찾을 수 있게 됩니다.

 

Median

어떤 배열에서 median을 찾기 위해서는 얼마만큼의 comparison가 필요할까요? Naive하게 생각해 보면, n-1 comparisons이 필요해 보입니다. Adversary argument를 가정한 input(알고리즘에게 최악인 입력)에 대해서 증명을 해 봅시다.

 

Find median of input

Input에서 mid를 기준으로 Large group과 Small group으로 나뉠 수 있습니다. Large나 Small group 내 비교는 crucial(결정적)합니다. 자기 위치를 정할 수 있기 때문입니다. 그러나 Large group의 element와 Small group의 element의 비교는 non-crucial합니다. 자기 위치를 정할 수 없기 때문이죠.

 

Mid를 찾기 위해서 element를 non-crucial element로 만들기 위한 비교를 수행합니다. 그리고 그 횟수는 총 ${n-1 \over 2}$가 됩니다. 그리고 각 그룹에서 비교를 통해 올바른 위치에 둔다고 하면 총 n-1의 비교가 필요하게 됩니다. 따라서 최소 ${3 \over 2}(n-1)$의 비교가 필요하다는 것을 알 수 있습니다.

 

Median을 찾는 문제의 Lower bound는 계속해서 증가하고 Upper bound는 계속해서 감소하고 있습니다. 아직까지 optimal 결과가 없는 문제입니다. 다음은 지금까지의 연구 결과입니다.

History of time complexity bound