Approximate Median , Selection Problem

우선 approxmiate median 에 대해 알아보기 전에, Quick Sort에 대해 간단히 짚어보자.

 

Quick Sort

저번 포스팅에서 Quick Sort의 평균 시간복잡도가 왜 O(nlogn) 인지 증명해보았다.

 

시간복잡도

• Average : O(nlogn)
• Worst : O(n^2)

피벗이 중간에 위치해 있다 -> Best Case

피벗이 한쪽 방향으로 계속 쏠려있다. -> Worst Case 

 

정말 운이 안 좋게도 재귀적으로 따라 들어갈 때마다 pivot 이 한쪽 끝이라면 시간복잡도가 O(n^2) 이다.

Quick Sort를 쓰는 의미가 없음.

 

시간복잡도 (최악의 경우)

• T(n) = n + T(n-1)
• T(n) = O(n^2)

이렇게 pivot의 위치에 따라 성능에 크나큰 차이가 발생한다.

따라서 이번 포스팅에서는 어떻게 해야 worst case 없이, 피벗을 야무지게 고를 수 있을지 알아보자.

 

---

Selection Problem

• In Quick Sort, How can we find the best pivot?
• If we can do it in O(N), QuickSort may run in O(nlogn)

O(N)으로 좋은 피벗을 찾으면, 퀵 소트는 O(nlogn) 에 풀린다는 뜻.

• (피벗의 왼쪽 element) < pivot
• (피벗의 오른쪽 element) > pivot

피벗에 의해 좌,우로 분할되고 Divide & Conquer 기법을 사용할 것이다.

따라서 Complexity : O(nlogn) 임은 자명하다.

 

그럼 여기서 다시, 어떻게 좋은 피벗을 고를 수 있을까?

Selection Problem

•  find the kth smallest elements in Array a.

배열 a 에서 k번째로 작은 원소 구하기.

O(nlogn) : Sort 함수 돌린 다음에 k 번째 선택하면 됨. 어렵지 않다.

 

Can we do anything faster? -> O(N)

O(N) 으로 k번째 원소를 고를 수 있을까?

 

결론부터 말하자면 O(N) 에 해결할 수 있다. Approximate Median 을 이용하는 것이다.

 

---

Approximate Median

우리가 정렬되지 않은 배열에서 정확히 중간값을 찾아내는 걸 O(n)에 하기에는 어렵다..

그래서 우리는 대략적인 중간값 (approximate median) 을 찾아보기로 했다. -> easier than find the exact median

 

Find a member among (a1 ~ an) where rank is between rn and (1-r)n

• 말 그대로 n개의 원소가 있는 배열에서 등수가 rn ~ (1-r)n 의 범위에 있는 값들을 찾는다는 의미이다.
• 0 < r < 1 

r = 0.3 일 때

r=0.3 일떄의 approximate median

0.3n ~ 0.7n 까지의 등수 범위를 보장하게 됨.

즉, exact median을 보장해주지는 않지만 어느정도 최적의 pivot 의 범위를 보장해줌으로써

한쪽으로 치우져진 값을 pivot으로 고르는 일은 막아준다. => no worst case.

• Quick Sort works in O(nlogn) with an Approximate Median.

 

---

Idea

• 배열을 5개씩 분할 (5개로 분할하는 이유는 뒤에 나오지만 r=0.3이기 때문이다.)
• 각 배열에서 5개 중에 중간값 찾기
• n/5 개의 중간값들 중에서 중간값 찾기

우선 n개의 원소를 가진 배열 a를 5개를 한 묶음으로 분할한다. 총 n/5 개의 분할된 배열이 생성.

(배열 a는 전혀 sorted 되어있지 않다.)

분할한 후, 각 분할에서 중간값을 구한다. -> O(n)

 

빨간색 별표시는 각 분할에서 중간값이다. 

원소는 5개뿐이며 이 경우 Selection sort를 활용하여 상수 시간에 median 값을 구할 수 있다.

 

각 분할마다 Median Value 를 구하는데 걸리는 시간 : O(N)

여기서 주의할 점은 빨간 별은 각 분할에서의 중간값일 뿐이다.

 

이렇게 하면 n/5 개의 중간값들이 만들어졌다. 이들 중에서 또 중간값을 구해 Approxmiate Median 을 구할 수 있다.

 

세로로 정렬

다음과 같이 빨간 별들(각 분할의 중간값들)에서 또 중간값 구함 : M 

M이 approximate median이다.

 

M을 기준으로 주황색 영역은 M보다 작다는 것이 자명하고, 파란색 영역은 M보다 크다.

• 빨간 별들 중 중간값을 구했으므로, 빨간 별 중 절반은 M보다 작고, 절반은 M 보다 크다.
• 이 별들은 또 각 분할에서의 중간값이다. 

위 두가지 특성을 이용해 M보다 작은 영역과(주황색) 큰 영역(파랑) 을 구할 수 있음.

비율을 계산해보면 대략 0.3n ~ 0.7n 사이에 든다. (중간에서 대략 60%)

이렇게 되기 때문에 처음에 5등분을 했던 것! -> n=0.3 이기 때문에

 

---

Performance

S(n) : Selection 시간

A(n) : Approximate median 구하는데 드는 시간

• A(n) 은 n이 5등분 된 상태, 즉 n/5개 중 중간값을 구하는 과정이므로 S(0.2n) 과 같다.
• n 은 5개씩 분할했을 때 중간값 구하는데 드는 시간이다.
• S(0.7n) : 최악의 상황을 가정하여 0.7n 이 주어졌을 때를 가정했다. 즉 pivot 이 오른쪽에 치우쳐져 있음.
• 피벗이 오른쪽 70% 지점에 있으므로 다시 Select 를 한다고 가정했을 때 : S(0.7n)

 

S(n) = n + S(0.2n) + S(0.7n)

 

S(n) = an + b   (이 부분은 나도 잘 모르겠다... 그냥 일반적인 경우 이렇다고 함)

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

 

방정식 풀면 a= 10, b = 0

S(n)의 시간복잡도 : O(n)

 

이렇게 우리는 O(n) 에 pivot 을 골랐다.