[서울대학교 논자시 준비] 알고리즘 : chapter 5 선택 알고리즘

평균 선형 시간 선택 알고리즘

 

n개의 원소로된 집합에서 최소 원소를 찾기 위해서는 O(n)의 사긴이 필요로한다. 그런데 n개의 원소 중 i번째 작은 원소를 찾기 위해서는 O(n^2) 의 시간이 든다.

 

정렬을 사용하면 O(nlogn)의 시간으로 단축할 수 있으므로 시간은 O(n)과 O(nlogn) 사이의 시간이 들 것이다.

 

알고리즘을 사용하면 O(n)의 시간에 확인할 수 있다고 한다. 

 

큰 몽둥이를 갖고 다니되 말은 부드럽게 하라

퀵정렬 알고리즘을 개선하면 평균적으로 선형시간에 i번째 작은 원소를 찾을 수 있게 한다.

 

알고리즘을 살펴보자.

 

소스코드

select(A, p, r, i)
{
if (p=r) then return A[p];
q<-partition(A, p, r);
k<-q-p+1;
if (i<k) then return select(A, p, q-1, i);
else if (i==k) then return A[q];
else return select(A, q+1, r, i-k);
}

 

분할 알고리즘이  리턴하는 값은 기준 원소가 전체에서 몇번째 작은 원소인지 알 수 있다. 그래서 그 값을 기반으로 i보다 더 작을 때는 작은 부분만 계속해서 재귀적으로 탐색하고, 더 크다면 더 큰 부분만 재귀적으로 탐색한다.

 

하지만 이 알고리즘은 평균적으로 선형 시간이 걸리지만 최악의 경우 O(n^2) 의 시간이 소요된다. 최악의 예는 분할 결과 0:n-1로 계속 분할이 되고 찾고자 하는 원소가 운 나쁘게도 큰 그룹에 속하는 일이 반복되는 경우이다.

 

이런 단점을 개선하고자 하는 알고리즘도 있다.

 

분할 균형 알고리즘은 최악의 경우에도 분할의 균형이 일정 비율 이상으로는 나빠지지 않도록 전처리함으로써 select알고리즘이 최악의 경우 수행시간이 O(n)이 되도록 만든 것이다.