Quick Sort의 시간 복잡도 계산

자세한 설명은 위키 참고 : https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

 

간단히 그림과 수식을 통해 계산해보자.

 

그림 설명

1. 최초 N개를 대상으로 pivot과 비교를 수행한다.(N-1이지만 근사)

2. 쪼개며 1이 될 때까지 동일하게 비교를 수행한다. 쪼개지더라도 전체로 보면 결국 N번 비교가 된다.

3. 2의 횟수는 logN이 될 것이다. 

결국, T(N) = N + (logN * N) = N*logN으로 계산된다.

 

 

수식 증명 : 위의 그림과 결국 같다.

T(N) = N + 2T(N/2)   

= 2T(N/2) + N

= 2(2T(N/4) + N/2) + N

= 4T(N/4) + N + N

= 4T(N/4) + 2N

= 4(2T(N/8) + N/4) + 2N

= 8T(N/8) + N + 2N

= 8T(N/8) + 3N

...

...                                           // x = logN <=> 2^x = N (log 밑 생략)

= 2^xT(N/2^x) + xN            // x회 반복 시 더 이상 쪼개지 않아도 된다. 즉 x회 반복 후 1로 모두 나눠진다는 의미이다.

= (2^logN * T(1)) + N*logN     

= 2^logN + N*logN             // T(1) = 1

= N + N*logN = N*logN

 

결론

위의 계산 법은 "평균적인" 시간 복잡도이며, Big O를 통한 시간 복잡도는 최악의 상황을 고려해야 한다.

이미 정렬되어 있는 배열을 대상으로 Quick Sort를 사용할 경우, N+(N-1)+(N-2)+....+2+1 = N(N+1)/2 = O(N^2)를 가지게 되기 때문에, 시간 복잡도는 N^2이 된다.