Find k th smallest in n array
물론 가장 간단한 방법은 sorting을 진행하고 k번째 인덱스에 접근하면 끝입니다. 그렇다면 가장 성능이 좋은 녀석은 무엇일까요?
일단 2가지 경우만 생각하도록 하겠습니다. 시간 복잡도가 nlogn이고, 공간 복잡도가 n인 in-place sorting만 생각을 하면 quick sort, heap sort로 한정이 되겠지요.
다시 이문제를 "selection" 문제라고 하자!!
Selection
이 문제를 풀어내는 방법에는 여러가지가 있다, 물론 Sorting 보다 빠른 방법으로 해야 이 문제를 푸는 의미가 있을 것이다.
- Quick sort
- 토너먼트
- Selection sort
- Approximate Median
Quick Sort
Quick sort를 K 근처에서 수행한다면 어떻게 될까?
최선의 경우 O(n)에 끝나지만, 최악의 경우O(n^2)이 걸리고 평균적으로는 O(n)이 된다.
토너먼트
토너먼트 방식을 사용하면 1등은 n, 2등은 n + logn, 3등은 n + 2logn, ..., k등은 n + klogn 이 걸리게 된다.
Selection Sort
selection sort를 k번째까지 수행한다면 kn 시간이 걸리고 만약에 k가 n/2이면 O(n^2)이 걸리게 된다.
Approximate Median
정의는 rn등부터 (1-r)n등 사이의 원소. (단 0 < r < 1).
- r = 0.3이라고 가정.
알고리즘은 다음과 같다.
배열을 5개로 분할하고, 각 분할의 중간 값을 찾아냅니다.
이 후 중간 값들 중 실제 중간 값을 찾습니다.
결론적으로 이 실제 중간 값은 반드시 rn등과 (1-r)n등 사이에 존재합니다.
위의 그림을 보면 배열을 5개로 분할(실제로 분할은 아님)하고 각 분할된 Array를 A1 ~ A5 (세로로)라고 하자.
이때 분할된 배열(빨간 영역과 같이)들을 정렬합니다. (위가 크고 아래가 작도록)
이 후, 가운데 값을 기준으로 각 분할된 배열을 정렬합니다. (편의상 안해도 됨, 실제 중간 값만을 찾기 위해서)
이 때 세로로 1, 2와 4, 5는 좌우로는 크기 비교를 할 수 없지만, 위 아래의 비교는 가능한 상태가 됩니다.
이때 분할된 배열(빨간 영역과 같이)들을 정렬합니다. (위가 크고 아래가 작도록)
이 후, 가운데 값을 기준으로 각 분할된 배열을 정렬합니다. (편의상 안해도 됨, 실제 중간 값만을 찾기 위해서)
이 때 세로로 1, 2와 4, 5는 좌우로는 크기 비교를 할 수 없지만, 위 아래의 비교는 가능한 상태가 됩니다.
위 그림에서 노란색으로 색칠해진 부분은 #보다 무조건 큰 값이 되고, 초록색으로 칠해진 부분은 #보다 무조건 작은 값이 됩니다. 따라서 대략적으로 #은 30% ~ 70% 위치에 있는 값이라는 것이 명확해 집니다.
이 것으로 대략적인 중간 값을 찾을 수 있게 됩니다. (Approximate Median)
자 이제 생각해 볼 것이 생겼습니다. Quick sort는 pivot을 찾을 필요가 있습니다. 또한 Approximate Median은 sorting을 할 필요가 있습니다. 어쩌죠?
"상호재귀함수"
그렇습니다. 어차피 둘다 필요하다면 서로를 호출하면 됩니다.
자 이제 Quick sort의 함수를 Q(), Approximate Median의 함수를 A()라고 합시다.
Q(n)은 A(n)으로 pivot을 찾습니다. 근데 이 때, pivot은 70% 안쪽이기 때문에 Q(0.7n)으로 호출하겠죠? (Quick sort는 왼쪽 오른쪽으로 나뉘어 재귀호출을 하기 때문에)
자 A(n)은 어떨까요? 아까의 로직을 되돌아보면 5개로 분할한다고 했습니다. 그리고 Quick sort를 사용하겠죠? 위 그림에서 세로로 sorting하는 것은 5개만 sorting하면 되기 때문에 계산에 넣지는 않겠습니다. 하지만 중간 값들을 sorting은 n과 관련이 있겠죠.
그 값은 n/5입니다. 따라서 A(n)에서 필요한 것은 Q(0.2n)이겠죠.
Q(n) + Q(0.7n) + Q(0.2n) --> t(n) + t(0.7n) + t(0.2n)
t(1.9n) --> O(n)