Worst-Case Linear-Time Selection(+퀵정렬)-알고리즘05

Worst-Case Linear-Time Selection

 

 

앞의 포스팅에서 분석한 바에 따르면

 

최상의 경우가 되기 위해  pivot을 고르는 방법은 언제나 n개의 배열의 원소가 있다면 그 중 $\frac{n}{2} $번째로 큰(혹은 작은) 원소를 pivot으로 정하는 것이었다.

2023.06.30 - [CS(Computer Science)/Algorithm] - QuickSort(2)-알고리즘03

QuickSort(2)-알고리즘03

이 pivot을 빠른시간에 고르는 알고리즘이 존재한다면 퀵정렬에 적용하여 최악의 경우에도 빠르게 정렬을 할 수 있는 퀵정렬을 만들 수 있을 것이다.

 

많이 알고있는 'binary search' (이진탐색) 알고리즘은 시간 복잡도가 O(nlogn)이다. 하지만 O(n)으로  $\frac{n}{2}$ 번째의 원소 x를 찾을 수 있는 알고리즘이 있다.

 

 

 

Algorithm

 

 

알고리즘 단계는 다음과 같다.

 

 

i번째로 작은 원소를 찾는다고 하자.

1. n개의 원소가 있는 배열에서 원소를 5개씩 묶어서  $\left \lceil \frac{5}{n}\right \rceil$ 개의 그룹을 만든다.
2. 각 그룹의 중간값을 찾는다. (이때 각 그룹마다 정렬을 해서 찾음)
3. 각 그룹의 중간값들의 중간값을 찾는다. 
4. 이 중간값을 X라하고 이를 기준으로 분할을 한다.
5. 분할 후 배열에서 X의 index를 K라하자. 그럼 X는 K번째로 작은 수이다.
6.  if i>k : X의 오른쪽 부분으로 재귀호출, if i==k : return X,  if i<k  X의 왼쪽 부분으로 재귀호출
7. 1~6 반복

 

 

 

Time-Complexity

 

 

이제 이 알고리즘의 시간복잡도를 계산해보자.

1. 번 과정 : O(n)
2. 번 과정: O(n)
3. 번 과정: T($\left \lceil \frac{5}{n}\right \rceil$)
4. ~7.번과정 : 수식으로 계산하자.

 

위의 사진의 원들은 배열의 원소고 각 세로줄에 5개의 원이 나열되어 있는데 이것이 하나의 그룹이다. x라고 표기된 원은 4번과정에서 찾은 X이다.

사진의 색칠한 부분은 X보다 크다고 확정된 원소들이다. 

---

 

예를들어 배열 [ (0,1,5,7,9),(2,4,8,10,11),(3,6,12,14,15),(20,21,22,23,24)] 에서 X가 2번그룹의 8이라 하자. 이때 8보다 무조건 큰 원소들은 10, 11 12 14 15 22 23 24이다. 

 (각 그룹의 중간값 5,8,12,22 의 중간값은 8(이라고하자 그냥)이고 각 그룹은 2번에 의해 정렬이 되어있다. 따라서 12의 그룹과 22의 그룹에서 8보다 크다고 확정된 원소들은 각 그룹내에서 12와 22의 우측에 있는 원소들이다.)

 

---

따라서,

X보다 큰값들은 "적어도" ($\left \lceil \frac{5}{n}\right \rceil$ $\cdot$ $\frac{1}{2}$-1 -1 )$\cdot$3 개 있다

(크다고 확정된 원소들이다.)

(그룹의 개수 $\cdot$ $\frac{1}{n}$ 는 X보다 작은 중간값들의 그룹들을 제외하는 것)

(-1 -1 은 X가 포함된 그룹과 마지막 그룹은 n이5로 정확하게 나누어지지 않아서  제외하는 것이라는데 이해가 안된다. 그냥 계산해도 될것 같다.)

 

 

 

($\left \lceil \frac{5}{n}\right \rceil$ $\cdot$ $\frac{1}{2}$-1-1)$\cdot$3  $\geq$ $\frac{3n}{10n}$ - 6

 

 

 

따라서 x보다 작은 원소수는 "최대" $\frac{7n}{10}$+6  (전체 n에 최소 X보다 큰 원소들의 개수를 뺸 것)개이다.

이 알고리즘은 최악의 경우를 가정하여 진행하기 때문에 언제나 $\frac{7n}{10}$+6 개의 원소에 대해 재귀적으로 반복한다고 하자.(x보다 작은 원소들의 수가 언제나 가능한 수중 최대라고 하자는 것이다)

 

 

 

따라서, 

4~7번에 의한 시간은 

T(n) $\geq$ T($\frac{7n}{10} + 6$) 이므로 

 

전체시간은 1번과정 ~7번과정 모두를 고려한

이 된다.

이제 이 식을 Substitution Method(귀납적 가설 방법)을 이용하여 풀면,

$T(n)$  $\geq$ $\frac{cn}{5}+c+\frac{7cn}{10}+6c+an$

 

=$\frac{9cn}{10}+7c+an$

 

=$cn+(\frac{-cn}{10}+7c+an)$

 

$\geq cn $      if : $\frac{-cn}{10}+7c+an \geq 0 $

 

이므로 T(n) = O(n) 이다.