QuickSort(2)-알고리즘04

Worst Case Partitioning

 

 

퀵 정렬의 수행시간은 분할 후 양쪽 구역의 크기가 비슷한지 그렇지 않은지에 따라 달라진다.

즉 퀵 정렬에서 pivot을 기준으로 분할을 할 때, pivot이 무엇이냐에 따라 연산횟수가 달라진다.

 

연산횟수를 최대로 만드는 pivot은 무엇일까?

일단 퀵 정렬의 시간복잡도는 T(n)= T(q) + T(n-q-1) + O(n) 이었다.

 

여기서 q가 n-1이라면 

 

T(n)= T(n-1) + T(1) + O(n)

 

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

 

=...

 

이다.

 

한마디로 배열을 n-1개짜리와 1개짜리 로 분할을 하는 pivot을 선택하는 것이 퀵정렬에서의 최악의 경우이다.

 

따라서 T(n)=O(n^2) 인데 이를 증명하자.

 

재귀트리를 이용하여 분석하면,

이므로 

$n+( \sum_{k=1}^n k)-1$ = $\Theta (n)+ \Theta( n^{2} )$ = $\Theta(n^{2})$  

 

 

 

 

Best Case Partitioning

 

최상의 경우로 pivot을 정하여 분할을 하는 방법은 크기 n의 배열을 

$\frac{n}{2} $ 과 $\frac{n}{2} $ 으로 나누는 것이다.

즉 

T(n)= T(q) + T(n-q-1) + O(n) 에서 q가 $\frac{n}{2}$ 이 되는 것이다.

 

T(n)= T($\frac{n}{2}$) + T($\frac{n}{2}$) + O(n)

 

=2T($\frac{n}{2}$) + O(n) 

 

이 식은 Substitution method 나 Master method를 이용하여 다음을 구할 수 있다.

 

T(n) = $\Theta(nlogn)$

 

 

 

 

Average Partitioning

평균적인 수행시간을 구하기: pivot이 될 수 있는 모든 경우의 수는 모두 발생 확률이 같다.

T(n) = T(q) + T(n-q-1) + O(n) 에서 

q= 0~ n-1 일때, 모든 경우를 더하고  이 합을 n(경우의 수)으로  나누는 것이 평균이다.

 

예를들어 n=3 이라면,

avg(T(3)) = $\frac{(T(0)+T(3-1)) + (T(1) + T(3-1-1)) + (T(2) + T(3-1-2))} {3}$

이다.

 

따라서 다음과 같이 T(n)을 구할 수 있다.

 

 

 

 

 

위 식은 다음과 같이 바꿀 수 있다.

 

 

 

 

결국 T(n)에 대하여 재귀식을 얻어 낼 수 있는데 이를 Substitution method를 이용하여 풀면 다음과 같다.

 

 

 

퀵정렬 평균 시간 계산

빨간색으로 표시된

$\sum_{k=1}^n klogk$   는 오른쪽의 식으로 인해서

 

$\frac{n^2 logn} {2} - \frac{n^2}{8} $  로 억지로 바꿀 수 있다.

 

또한 $\frac{2b}{n}$ 은 충분히 큰값의 n에 대해 고려할 필요가 없을 정도로 작기 때문에 $\Theta(n)$에 귀속된다고 해여도 무방하다.

 

 

결국 T(n) <= anlogn + b 를 도출해 내었고 퀵정렬의 평균시간은 O(nlogn)이다.

 

 

---

이번 포스팅에서는 worst case, best case, average case 각각에 대하여 수행시간을 분석해 보았다.

다음 포스팅에서는 최악의 경우 선형시간 선택 알고리즘(worst case linear selection)를 이용하여 최악의 경우에도 퀵정렬의 수행시간이 O(nlogn)이 되도록 만들 수 있는데 이에 대하여 알아보겠다.