[알고리즘] 선택 알고리즘(Selection Algorithm)
옛날에 배운 것들 다시 정리하는 시간들을 가지려고 한다. 시간이 되면 철학과에서 배운 것들을 다시 정리하고 싶기도 하다.
1. 선택 문제 (Selection Algorithm)란?
* Input: A[1...n] and integer i (1 <= i <= n)
* Output: i-th smallest number in A
* Time complexity : Averge O(n) / Worst O(n)
선택 문제란, 배열에서 i번째로 작은 수를 추출하는 문제를 일컫는다. 잠깐 생각해 보면 sorting(O(nlogn))으로 간단히 풀 수 있을 것 같지만, O(n) 알고리즘이 존재한다.
2. 선택 문제 알고리즘 - Average Theta(n)
1) 작동 방식
2) 코드
int select(int* A, int p, int r, int i) {
if(p==r) {
return A[p];
}
int q = partition(A, p, r);
int k = q-p+1;
if(i<k) {
return select(A, p, q-1, i);
}
else if (i==k) {
return A[q];
}
else {
return select(A, q+1, r, i-k);
}
}
퀵소트랑 비슷~하게 생겼다. partition함수는 p와 r 사이의 랜덤 피벗을 찾아주는 함수이다. 이전 포스팅에 수도 코드를 올렸었는데, 다시 올려 보자면
partition(A[], p, r){
pivotElement <- A[r];
i<- p-1;
for(j<-p to r-1){
if(A[j]<=pivotElement)
then A[++i] <-> A[j];
}
A[i+1] <-> A[r];
return i+1;
}위와 같다. 자세한 설명은 퀵소트 관련 포스팅을 참고하길 바란다.
1. 마지막 원소를 피벗으로 잡고, 시작점에 i, 그 다음에 j를 위치시킨다.
2. j에 피벗보다 작은 원소가 나올 경우 i를 증가시키고 i의 원소와 j의 원소를 스왑한다.
3. j를 증가시키면서 2를 반복한다.
4. 마지막에 i 다음 위치에 피벗원소를 이동시킨다.
시간복잡도를 계산하자면, 여기 수식을 넣는 법을 모르겠는데,
3) 평균적인 경우의 Time complexity
1. O(n)
2. Omega(n)
Omega(n)도 성립한다. 왜냐하면 내가 처음에 딱! 잡은 그 pivot 원소가 i번째 원소였을 때, partition 에서 최소 n에 비례하는 정도만큼은 움직여 줘야 하기 때문이다. 대부분의 책에서 '자명하다'라고 나와 있는데, 나는 이렇게 이해했다.
3. Theta(n)
1, 2에 따라 T(n) = theta(n) 이다.
4) 최악의 경우의 Time complexity
최악의 경우에는, partition 알고리즘에 따라 항상 0:n-1로 분할된다. 따라서
T(n) = T(n-1) + Theta(n)
T(n) = Theta(n^2)
가 성립한다.
최악의 경우 시간복잡도가 크다. 따라서 Worst-case에도 O(n)이 걸리는 알고리즘을 알아보자. 신기한 방법이다.
3. 선택 문제 알고리즘 - Worst Theta(n)
1) 아이디어
위 알고리즘의 문제 : 균형 잡힌 partition이 보장되지 않음
문제 : 균형 잡힌 partition을 보장하려면, pivot이 대충 중앙값이라는 것을 알 방법이 필요하다.
그런데 이 방법은 recursive 아니면 sorting(O(nlogn))밖에 없다.
Idea : 상수 개의 원소들(예를 들어 5)로 쪼개서 각 그룹마다 sorting해서 중앙 비슷한 값을 알아내자.
- 상수개만 sorting하므로 시간복잡도도 상수
2) 동작 방식
사실 중요한 아이디어는 피벗 원소를 balanced로 잡는 것이기 때문에, 뒤는 그냥 일반 selection algorithm과 같다. 참고로, 5보다 작은 길이의 배열이 들어올 경우, 그냥 정렬해서(역시 상수시간) 찾아서 리턴하면 된다.
여기서 Insertion sort를 활용하는 이유는, sorting이 되어있을 확률이 크고, insertion sort가 간단하고, 어차피 상수시간이기 때문에 그렇게 복잡한 로직을 넣을 만큼 애쓰지 않아도 되기 때문이다.
3) Worst-case Time complexity
1. 어떤 경우가 Worst-case인가?
예를 들어 11개의 원소에서 partition한다고 생각해 보자.
위 예시에서는 3:7이 worst partition이다. 이를 위해서 원래는 M과의 관계를 알 수 없는 원소들을 한쪽으로 몰아넣었다. 이 느낌을 가져가면서 아래 일반화를 보자.
따라서 worst case partition은 3:7이 된다. 0:n-1보다는 낫다.
2. Worst-case Time complexity
4) Why 5?
한 그룹이 5개 원소씩 갖도록 나누는 이유는 이 worst-case Theta(n)을 보장하기 위해서이다. 꼭 5가 아니어도 되긴 하겠지만, 대충 5가 제일 적합하다고 한다. 절대 안되는 경우는 한 그룹이 3개 원소씩 갖도록 나누는 것이다.
보장이 안된다.