[CLRS] [7-2] Performance of quicksort (퀵정렬의 시간복잡도)

0. Intro

- 7-1에서 우리는 Quicksort를 직접 구현해보았다.

- 이번 챕터에선 Quicksort의 시간복잡도를 한번 구해보고자 한다.

- 엄밀하게 증명을 통해 구하기 보단, 직관적으로 이해하기 쉽게 알아보고자 한다.

 

1. Best cases

- 최선의 경우 분할할 때 정확히 절반을 계속 나누는 것을 의미한다.

- 깊이는 O(logn)이고, 각 순환 호출에서의 비교 연산은 O(n)이다.

- 따라서 최선의 상황의 시간복잡도는 O(nlogn)이 된다.

 

2. Worst Cases

- 최악의 경우는 정렬하고자 하는 배열이 오름차순으로 정렬되어 있거나,

- 내림차순으로 정렬되어 있는 경우이다.

- 깊이는 O(n)이고, 각 순환 호출에서의 비교 연산은 O(n)이므로 

- 따라서 최악의 상황의 시간복잡도는 O(n^2)이 된다.

 

3. Averge cases

- 우리가 n-1번 분할하는 동안 모두 최솟값이나 최댓값을 고를 확률은 매우 작다.

 

--> n개의 배열에서 1번 최댓값이나 최솟값을 고를 확률은 2/n이다.

--> 모든 파티셔닝에서 최솟,최댓값을 고를 확률은 (2/n)^(n-1)이다.

 

- n이 커지면 커질수록 이 확률은 0에 점점 수렴하게 된다. 

- 따라서, 거의 대부분의 경우 최댓값, 최솟값이 아닌 값을 고르게 되므로,

- 결과적으로 QuickSort는 logn에 가까운 횟수로 수렴하게 된다.

- 즉 평균적인 상황에서의 시간복잡도는 O(nlogn)이 된다.