퀵소트(Quick Sort) 의 시간복잡도(Time Complexity)

오늘 알고리즘 수업을 듣다가 Time Complexity 계산방법에 대한 강의 중에 누군가 수업시간에 한 질문,
"우리가 흔히 nlogn 정렬이라고 말하는 퀵 소트의 경우 Worst Case 는 O(n^2) 이 된다. 교수님이 설명하시길 알고리즘의 시작복잡도는 Worst Case 를 기준으로 측정한다고 얘기했는데 퀵소트는 Average Case 를 기준으로 할 때만 O(nlogn) 이 되는 것인데, 그렇다면 과연 퀵 소트를 O(nlogn) 정렬이라고 정렬이라고 부르는 것이 맞는가?"

참고로, 머지 소트(Merge Sort) 와 힙 소트(Heap Sort) 의 경우 Worst Case 에서도 O(nlogn) 에 수행된다.

당시 알고리즘의 Time Complexity 는 Worst Case 를 기준으로 측정한다고 설명하던 강사도 이 질문에 살짝 당황해서 좀 버벅이다가 실제 상황에서는 Average Case 를 대상으로 적용하는 경우가 많기 때문에 퀵 소트를 nlogn 정렬이라고 본다고 설명했다.

평소에 당연히 퀵 소트는 O(nlogn) 이라고만 생각하던 차, 이 질문을 듣고 나도 의문이 생겨서 집에 와서 CLRS 책을 다시 뒤져보았다.

"Quicksort is a sorting algorithm whose worst-case running time is O(N^2) on an input array of n numbers, In spite of this slow worst-case running time, quicksort is often the best practical choice for sorting because it is remarkably efficient on the average: it's expected running time is O(nlogn), and the constant factors hidden in the O(nlon) notation are quite small. It also has the advantage of sorting in place and it works well even in memory environments.

그러니까, Quicksort 는 O(nlong) 에 숨어있는 상수 계수의 크기도 작고, 내부 정렬이며, 평균적으로 가장 빠르게 수행되는 정렬이며, 가상메모리 상에서도 잘 동작하는 일반적으로 가장 좋은 정렬이다는 이야기. partition 의 깊이 logn 과 각 partition 에서의 비교횟수 n 번이 수행되어 Average Case 는 O(nlogn), n-1 과 0 으로 partition 되는 경우 Worst case O(N^2) 이 된다.

결론적으로 Worst-case 가 알고리즘의 시간복잡도를 평가하는 절대적인 기준은 아니란거네..

Average Case 는 대개 계산하기도 힘들고, 현실에서는 입력되는 값의 정확한 분포를 알기 어려우므로 쓰기 힘들다. 
Worst Case 는 알고리즘의 성능을 보여주는 척도가 될 뿐만 아니라 경험적으로 알고리즘의 수행시간은 Worst Case 인 경우의 수행시간과 큰 차이가 나지 않기때문에  일반적으로 알고리즘의 시간복잡도를 말할때는 Worst-Case 기준으로 평가한다.
"어떤 알고리즘의 시간복잡도가 O(n^2) 이라면 이 알고리즘은 최악의 경우 n^2 만큼 수행한다." 는 의미가 된다.

결론적으로 강사가 이런 부분을 명확하게 설명을 안해준거네 -0-