[ Divide and Conquer ] The Selection Problem & Approximate Median

O notation에서 상수가 차이가 나기 때문에, 이 안에서 어떤게 더 좋을지 판단할 수 있다. 

그런 류의 아주 복잡한 문제를 Quick Sort가 만들어낸다. 

 

앞으로 이야기 하는 이야기에서는 Quick Sort가 그렇게 좋지 못하다는 것을 알게 될 것임.

 

*Worst일 때는 merge sort가 더 좋다. 

우리는 이걸 O(NlogN)으로 만들고 싶다.

실제로는 merge보다 quick이 빠르다. 따라서 worst case만 고치면 O(NlogN)이 되면서 merge보다 빠르게 될 것이다.

 

In Quick Sort : can we Find the Best Pivot?

if we can do it in O(N), Quick Sort will run in Worst Case O(NlogN) time

따라서, 우리는 중간 값을 어떻게 select할 것인지에 대해 고민해야한다. 

 

Selection Problem

Find the k-th smallest among \(a_1\), \(a_2\), ... \(a_n\)

-> K에 따라 Minimum, Maximum, Median, Selection 등을 선택할 수 있는 것이다. 

O(NlogN) is easy, Just Sort and look at the k-th : sorting해서 구하면 되니까 NlogN은 쉽다.

 

Minimum, Maximum은 쉽다.

Median을 풀 수 있다면, Selection을 찾을 수 있다.

-> Median을 몇번씩 해서 Selection을 하면 O(logN)에 풀 수 있다.  

-> Minimum을 k-1 반복해서 Selection을 하면 O(\(n^2\)에 풀 수 있다. 

 

BUT ANYTHING FASTER? 

결국 우리는 O(N)에 풀 수 있도록 할 것이다. 

 

The Approximate Median Problem

대충 중간에 있는 것

 

Find among \(a_1\), \(a_2\), ... , \(a_n\), a member whose rank is between rn and (1-r)n

0 < r < 1

Let's fix r at 0.3

 

즉, 중간에 있는 애들을 말할건데, 중간 40% 정도를 approximate Median이라고 할 것이다. 

 

 

이 approximate Median만 있어도, Quick sort가 빨리 끝나게 할 수 있음

 

어떻게?

Approximate Median을 찾아서 이를 pivot으로 찾아서 돌린다면 최악의 경우 O(NlogN)이다.

approximate median에서 최악의 경우는 맨 끝 30%에 가는 것이다. (직관적으로)

T(n) = T(0.3n) + T(0.7n) + n

T(n)을 anlogn + bn + c로 두겠다.

anlogn + bn + c = 0.3anlog(0.3n) + 0.3bn + c + 0.7anlog(0.7n) + 0.7bn + c + n

a nlogn= a(0.3+ 0.7)nlogn + an x log0.21 + c + n

c = 0 이 되므로 a x log0.21 + n 이 0이 되면 된다. 

a = \(-\frac{1}{log0.21}\) > 0, b = 0, c = 0

따라서 NlogN으로 만들 수 있다. (a만 해가 있으므로)

approximate Median을 찾을 수 있으면 NlogN으로 돌릴 수 잇다. 

 

Selection Strategy with Approximate Median

Selection을 하는 문제에 대해 이야기해보자.

• Find Approximate Median as P
• (As in Quick Sort) Divide array using P

피벗을 나누자, quick sort에서 하듯이.

이러면, 피벗을 기준으로 왼쪽은 다 피벗보다 작고, 오른쪽은 다 크다. 

만약, k번째가 왼쪽에 떨어진다면 피벗 뒤쪽을 신경쓸 필요가 없다

만약, k번째가 오른쪽에 떨어진다면, 피벗 앞쪽을 신경쓸 필요가 없다 

>> 해당 과정을 재귀로 구현할 수 있음

 

pivot = mediam : T(n) = T(n/2) + n ... = O(n) 등비수열의 합이라서 

pivot = A.M : T(n) = T(0.7n) + n = T(\(0.7^2\) + 0.7n + n = O(n) -> 곱해진 상수는 mediam보다 큼

작은게 아무리 작아도 30%를 하기 때문에, 최악의 경우는 30% 부분보다 70% 부분이 최악이다.

 

A.M과 Selection은 아주 밀접한 관련이 있다. 

 

Approximate Median Strategy

• Fixed r at 0.3
• Divide into 5 memebers :들어오는 입력 그대로 5개로 자름
• Sort each 5-member set : 5개 그룹을 나눈 것을 각각 sorting함 -> 그냥 5가 상수기 때문에 상수 시간이 걸림
• Find Real Median X among the Medians of 5 members 
• X Turns out to be an Approximate Median

5개 그룹에서 각각 3등인 애들만 모았다. => 가운데 기준으로 sorting을 했고, 나머지가 따라 움직였다고 생각하자 (실제로 x)

그 가운데 애들 중, 가운데가 median이다. 이걸 X라고 하겠다.

확실히 작은 애들은 왼쪽 아래 파란 부분이 되고, 확실히 큰 애들은 오른쪽 보라색 부분이 될 것이다. 

 

파란부분이 30%, 보라색 부분이 30% 이므로 40% 가량 정확한 Approximate Median을 찾을 수 있다.

하지만, 현재는 3등 부분에서 sorting을 하는 과정이 없어야하고, 지금 A.M을 찾기 위해 Median을 구해야하는 상황이 발생했기에 현재 이 아이디어에서 수정이 들어가야한다. 

 

Analysis of Selection with A.M

5개 그룹에서 그룹별 sorting -> O(n)

n/5개에서 Median을 찾아야함 -> Selection 사용

* Selection을 하기 위해 A.M을 사용하고 A.M을 하기 위해서 Selection 을 사용

 

S(n): n개짜리 selction 을 하는 알고리즘 

A(n) : n개에서 A.M을 찾는 알고리즘

S(n) -> A(n) -> p로구분 (O(n)) -> S(0.7)

A(n) -> O(n) 그룹 계산 -> S(0.2n)

 

Selection 하는데 걸리는 시간 : S(n) = S(0.2n) + S(0.7n) + n

S(n) = an + b

an+b = 0.2an + b + 0.7an + b + n

an + b  = (0.9a + 1)n + 2b

b = 0, a = 10

S(n) = 10n = O(n)

 

>> 이를 Quick sort에 넣으면 O(NlogN)에 돌아가도록 할 수 있다. 
그렇지만, merge sort보다 Quick sort가 빠른 이유는 배열을 추가로 할당하지 않아서 그런건데, A.M을 찾으려면 추가로 배열을 할당해야하는데 실제로는 Quick sort가 merge sort보다 느리게 된다.