> [!warning] > 이 페이지는 아직 미완성입니다. 주어진 데이터를 정렬하기 위해 다음의 과정을 거친다. 1. 주어진 데이터 중 하나를 pivot으로 선정한다. 2. pivot을 기준으로 데이터를 둘로 나눈다. 3. 나눈 데이터에 대해 1번과 2번을 다시 적용한다. 이것을 Recurrence Equation으로 표현하면 다음과 같다. $ T(n) = T(m_1) + T(m_2) + cn \space(m_1+m_2 = n-1) \text{ if }n>1 \newline T(1) = 1 $ 이때 pivot을 잘 고르면 데이터가 merge sort처럼 항상 둘로 깔끔하게 떨어지고, 그렇지 않다면 최악의 경우 데이터가 항상 1:n-1로 나뉘어 (n-1)번의 분할을 거쳐야 한다. 따라서 Quick Sort가 가질 수 있는 최선의 시간 복잡도는 O(nlogn)이고, 최악의 시간 복잡도는 $O(n^2)$이다. 데이터를 분류하는 과정이 O(n)의 시간 복잡도를 가지기 때문이다. Recurrence Equation으로 최선의 경우와 최악의 경우를 나누면 다음과 같다. $ T(n) = T(n-1) + cn, \space\text{if }n>1\newline T(1) = 1 $ $ T(n) = 2T(\frac{n}{2}) + cn, (n\ge2) \newline T(1) = 1 $ 또한 평균 시간 복잡도를 구하는 Recurrence Relation이 다음과 같기 때문에, 평균 시간 복잡도는 O(nlogn)이다. $ T(n) = \sum_{p=1}^{n}\frac{1}{n}\{T(p-1)+T(n-p)\}+cn\newline T(0) = 1 $ 이를 증명하기 위해서는 수학적 귀납법과 부분적분이 필요하다. 평균 시간 복잡도를 재귀적으로 계산할 때 주목해야 할 부분은 모든 케이스가 2번씩 등장한다는 것이다. 따라서 점화식을 다음과 같이 정리할 수 있다. $ T_{ave}(n)\le cn+\frac{2}{n}\sum_{p=0}^{n-1}T_{ave}(p)\text{ for all }n\ge2,\newline T_{ave}(1), T_{ave}(0)\le b $ 여기에 더해 k = 2(b+c)라 할 때, 2보다 같거나 큰 모든 정수 n에 대해 $T_{ave}(n)\le kn\log_en$이 성립한다. 이때 $\log_en \le \log_2n$이므로 평균 시간 복잡도는 O(nlogn)이 된다.