퀵소트는 피봇을 정하는 파티션 과정과 2번의 분할 과정으로 이루어져 있다. \(n\)개의 원소를 퀵소트로 정렬하는 데 걸리는 시간을 \(T(n)\)이라 할 때 \(T(n)\)은 \(m\)개와 \(n-m\)개로 분할된 원소를 정렬하는 시간과 \(n\)개의 원소 중 피봇을 정하는 파티션 과정으로 나눌 수 있다. 아래 식을 활용해서 퀵소트의 시간복잡도를 구할 수 있다.
$$T(n) = T(m) + T(n-m) + C(n) $$
Best case time complexity
퀵소트는 피봇이 항상 배열을 균등하게 분할하여 분할의 횟수가 \(\log n\)번 실행되는 경우에 \(O(n\log n)\)에 동작한다. 최선의 방법으로 퀵소트를 할 때 걸리는 시간을 \(T(n)\)이라고 하면 \(T(n)\)은 아래와 같다.
$$T\left(n \right)=2T\left( \dfrac{n}{2}\right) + n \ \cdots \ \text{①}$$
이 때 ①의 \(n\)에 \(n-1\)을 대입하여 \(T(\dfrac{n}{2})\)을 구할 수 있다.
$$T\left( \dfrac{n}{2}\right) =2T\left( \dfrac{n}{4}\right) +\dfrac{n}{2} \ \cdots \ \text{②}$$
①에 ②을 넣은 후 규칙을 찾은 후 \(T(n)\)을 일반화 해보자.
$$\begin{aligned}T\left( n\right) &=2\left\{ 2T\left( \dfrac{n}{4}\right) +\dfrac{n}{2}\right\} +n\\
&=2\left[ 2\left\{ 2T\left( \dfrac{n}{8}\right) +\dfrac{n}{4}\right\} +\dfrac{n}{2}\right] +n\\
&=2^{k}T\left( \dfrac{n}{2^{k}}\right) +kn \end{aligned}$$
이 때, 배열의 분할 회수는 \(k\)는 \(\log n\)과 같으므로 \(T(n)\)을 다음과 같이 바꿀 수 있다.
$$\big( k= \log _{2}n\big) \Rightarrow \big( T\left( n\right) = nT\left( 1\right) +n\log _{2}n \big) $$
1개를 정렬하는데 걸리는 시간은 0이므로 \(T(1) = 0\)이고 \(T(n)\)의 시간복잡도는 아래와 같다.
$$ \begin{aligned} \therefore T(n) &= O\left( 0 + n\log_{2} n \right) \\ &= O\left( n\log n\right) \end{aligned} $$
Worst case time complexity
퀵소트는 배열이 이미 정렬된 경우 피봇을 항상 첫 번째 인덱스 혹은 마지막 인덱스를 선택할 때 \(O(n^2)\)에 동작한다.
$$\begin{aligned}T\left( n\right) &=T\left( 1\right) +T\left( n-1\right) +n\\
&=T\left( n-2\right) +2n \quad \big( \because T\left( 1\right) =0\big)
\\
&=T\left( 1\right) +n^{2}\\
\therefore T \left( n\right) &=n^{2}\\
&=O\left( n^{2}\right) \end{aligned}$$
Average case time complexity
퀵소트의 평균 시간복잡도를 구하기 위해 아래와 같은 가정이 필요하다.
- 피봇은 랜덤 하게 선택되며 배열의 \(n\)개 원소가 각각 피봇으로 선택될 확률을 \(\dfrac{1}{n}\)으로 같다.
- 배열의 \(n\)개의 원소를 랜덤 하게 선택된 피봇으로 퀵소트 할 때 걸리는 평균 시간을 \(T(n)\)이라고 하자.
피봇이 배열의 \(k\)번째 \((1 \le k \le n)\) 원소라면 \(k\)번째 원소를 기준으로 수행한 파티션 과정은 \(n-1\)번의 비교 연산을 수행하며 그 결과 입력의 크기는 \((k-1)\)개와 \((n-k)\)개로 분할된다. 따라서 \(T(n)\)은 아래와 같다.
$$\begin{aligned}T\left( n\right) &=\dfrac{1}{n}\sum ^{n}_{k=1}T\left( k-1\right) +\dfrac{1}{n}\sum ^{n}_{k=1}T\left( n-k\right) +\dfrac{1}{n} \sum ^{n}_{k=1}(n-1)\\
&=\dfrac{2}{n}\sum ^{n}_{k=1}T\left( k-1\right) +(n-1)\end{aligned}$$
양 변에 \(n\)을 곱한 후 ①을 얻고, ①에 \(n=n-1\)를 대입하여 ②을 얻는다.
$$ \begin{aligned}nT\left( n\right) &=2\sum ^{n}_{k=1}T\left( k-1\right) +n\left( n-1\right) \ \cdots \ \text{①} \\
\left( n-1\right)T\left( n-1\right)&=2\sum ^{n-1}_{k=1}T\left( k-1\right) +\left( n-1\right) \left( n-2\right) \ \cdots \ \text{②} \end{aligned} $$
이 때, \(\text{①}-\text{②}\)을 하면 아래와 같다.
$$ \begin{aligned}nT\left( n\right) -\left( n-1\right) T\left( n-1\right) &=2T\left( n-1\right) +2\left( n-1\right) \; \left( \because\text{①}-\text{②} \right) \\
nT\left( n\right) &=\left( n+1\right) T\left( n-1\right) +2\left( n-1\right) \end{aligned} $$
양변에 \(\frac{1}{n(n+1)}\)를 곱한다.
$$\begin{aligned}\dfrac{T\left( n\right) }{n+1}&=\dfrac{T(n-1)}{n}+\dfrac{2\left( n-1\right) }{n\left( n+1\right) }\\
&=\dfrac{T\left( n-1\right) }{n}+\dfrac{2\left( n-1\right) }{n}-\dfrac{2\left( n-1\right) }{n+1} \ \cdots \text{③} \end{aligned}$$
이 때, \(n=n-1\)을 대입하여 \(\dfrac{T(n-1)}{n}\)을 구하면 아래와 같다.
$$\begin{aligned}\dfrac{T\left( n-1\right) }{n}&=\dfrac{T(n-2)}{n-1}+\dfrac{2\left( n-2\right) }{\left(n-1\right) n }\\
&=\dfrac{T\left( n-2\right) }{n-1}+\dfrac{2\left( n-2\right) }{n-1}-\dfrac{2\left( n-2\right) }{n} \ \cdots \text{④}\end{aligned}$$
④를 ③에 대입하면 아래와 같다.
$$ \dfrac{T\left( n\right) }{n+1}=\dfrac{ T( n-2) }{n-1}+\dfrac{2\left( n-1\right) }{n}-\dfrac{2\left( n-1\right) }{n+1}+\dfrac{2\left( n-2\right) }{n-1}-\dfrac{2\left( n-2\right) }{n} $$
이 과정을 T(1)까지 진행하여 \( T(n) \)을 구할 수 있다.
$$\begin{aligned}\dfrac{T\left( n\right) }{n+1}&=\dfrac{T\left( 1\right) }{2}-\dfrac{2\left( n-1\right) }{n+1}+\dfrac{2}{n}+\dfrac{2}{n-1}+\cdots +\dfrac{2}{3}+\dfrac{2}{2} \ \left( \because T(1) = 0 \right)\\
&=-\dfrac{2\left( n-1\right) }{n+1}+2\sum ^{n}_{x=2}\dfrac{1}{x}\\
&=2\sum ^{n}_{x=1}\dfrac{1}{x}-\dfrac{4n}{n+1}\\
\therefore T\left( n\right) &=2\left( n+1\right) \sum ^{n}_{x=1}\dfrac{1}{x}-4n\end{aligned}$$
이 때, \(\sum ^{n}_{x=1}\dfrac{1}{x}\)은 \(\log _{2}n\) 보다 작다.
$$ \sum ^{n}_{x=1}\dfrac{1}{x} <\int ^{n}_{1}\dfrac{1}{x}dx=\ln {n} <\log _{2}n $$
따라서 \(T(n)\)의 시간복잡도는 아래와 같다.
$$\begin{aligned}T\left( n\right) &=2\left( n+1\right) \sum ^{n}_{x=1}\dfrac{1}{x}-4n <2\left( n+1\right) \log_{2}n-4n\\
\therefore T\left( n\right) &=O\left( 2\left( n+1\right) \log_{2} n-4n\right) \\
&=O\left( n\log n\right) \end{aligned}$$