1. Selection Problem and Approximate Median
quick sort에서 우리는 어떻게 가장 좋은 pivot을 얻을 수 있을까?
만약 우리가 O(N)에 best pivot을 뽑으면 최악의 경우가 O(nlogn)가 되지 않을까?
Selection Problem 은 k번째 작은 것들을 찾는 것이다. 이것은 median을 찾는것과 비슷한 시간복잡도는 갖는다.
Selection Problem을 O(nlog)으로 구현하는 것은 쉽다. 그냥 sorting 하면되기 때문이다.
하지만 O(nlog)은 필요가 없다.
2. Selection Approximate Median with Quick Sort
pivot으로써 Approximate Median을 찾으면 quick sort를 O(nlogn)에 할 수 있다.
median을 찾는것보다 median 쯤을 찾는 것이 더 쉽다.
(median을 찾으면 median쯤을 알 수 있는데 median쯤을 찾으면 median을 알 수 없으므로)
Approximate Median은 [r*n, (1-r)n]을 찾는 것이다. 여기서 r은 0<r<1인 값이다.
만약 r이 0.3이라면 0.3n<x<0.7n 을 찾게된다. 즉, 중심 40%를 찾으라는 의미가 된다.
Quick Sort를 이용해서 Selection problem을 해결할 수 있다.
Quick Sort에서 pivot을 기준으로 왼쪽 오른쪽으로 분류한 것과 같이 나눈 뒤 k등이 pivot 보다 왼쪽에 있으면 왼쪽 부분만 재귀적으로 Selection을 수행한다. k등이 pivot보다 오른쪽이면 오른쪽 부분만 재귀적으로 Selection을 수행한다. 이 과정을 반복하면 시간만에 k등 원소를 찾을 수 있다.
시간복잡도는 아래와 같다.
- pivot이 중간값 (Median)인 경우:
- pivot이 Approximate Median() 인 경우:
r=0.3일때 Approximate Median 을 찾는 알고리즘을 알아보자.
| OOOOO | OOOOO | ... | OOOOO |
원소들을 5개씩 잘라서 하나의 그룹으로 만들고 그 그룹 내에서 정렬을 하면 O(n) 시간안에 정렬이 된다.
(아래에서 위 방향으로 커지게 정렬)
| o o |
o o |
... | o o |
o o |
| o | o | ... | o | o |
| o o |
o o |
... | o o |
o o |
이제 각 그룹 내에서 중간값 (3등) 들끼리 모아서 5묶음을 Sorting 되었다고 가정한다.
(실제로 정렬하진 않음, 나머지는 따라 움직인다고 생각)
3등들끼리 모은 배열에서 또 중간값을 Median X(초록색)라고 하자.
이 경우 배열 전체에서 30%, 즉 0.3n개 (노란색)는 항상 X보다 작고,
30%, 즉 0.3n개(하늘색) 는 항상 X보다 큼을 알 수 있다.
따라서 X는 Approximate Median이 된다.
4. 성능 ( Approximate Median으로 selection )
1. n개에서 Approximate Median을 푸려면 5개끼리 묶어서 그룹화 후 5개씩 sorting ()
2. n/5개의 중간값들 중 Median을 찾아야한다. 근데 여기서는 n/5개짜리 Selection을 해야 한다.
(Selection을 하기 위해 Approximate Median을 쓰는데 그 안에 n/5개짜리 Selection이 있는 셈)
S(n) = A(n) + O(n) + S(0.7n)
S를 Selection을 하는 시간, A를 Approximate Median을 하는 시간이라고 하자.
A(n)은 n개짜리 Approximate Median 알고리즘을 돌린다.
S(0.7n)은Selection을 다시 호출한다. (최대 Size:
A(n) = O(n) +
O(n) 은 5개씩 나누는 시간이다.
S(0.2n)은 n/5개짜리 Selection 시간하는 시간이다.
여기서 0.2와 0.7의 합이 1보다 작기 때문에 O(n)이 걸렸다.
만약 1이면 O(nlogn)의 시간이 걸렸을 것이다. 그래서 아까 1/5씩으로 끊은 것이다.
증명해보기 위해 S(n) = ax+b 라고 해보자.
S(n) = 0.2a+b +0.7a+b+n= (0.9a+1)n + 2b
a가 10이고 b가 0 가 나온다.
따라서 S(n) = 10n = O(n) 이 된다.
Approximate Median에서 sorting 하는 과정은 없다.
sorting한다고 가정하는 것이다. 실제로는 개수만 센다.
하지만 Approximate Median은 추가 메모리를 할당받아야해서 merge sort를 이용하는게 더 효율적일 수 있다.
따라서 이는 잘 안쓴다.
'학부 내용 정리 > [ 2-2 ] 알고리즘' 카테고리의 다른 글
| [ 알고리즘 ] Convex Hull : CCW, Brute-Force-ish, Package Wrapping, Graham Scan, Plane Sweeping, Divide and Conquer, Farthest Point (2) | 2022.10.18 |
|---|---|
| [ 알고리즘 ] Closest pair (0) | 2022.10.17 |
| [ 알고리즘 ] Divide and Conquer : Quick Sort (0) | 2022.10.15 |
| [ 알고리즘 ] Tape Storage (1) | 2022.10.14 |
| [ 알고리즘 ] Deadline Scheduling (0) | 2022.10.14 |