[알고리즘설계] 퀵소트의 ‘평균’시간복잡도

[알고리즘설계] 퀵소트의 ‘평균’ 시간복잡도

---

개요

• 퀵소트의 시간복잡도는 O(nlogn)으로 알려져있지만, 최악의 경우 O(n^2)일 수있다. 그래서 퀵소트의 ‘평균’ 시간복잡도 를 구해보려 한다.
• 최악의 경우인 O(n^2)의 상황은 사실 극히 드물다. 피벗의 선택기준을 맨앞이나, 맨뒤로 했을 경우에 이미 정렬이 되어있는 경우 등이 있을 것이다. 퀵소트의 기본 아이디어는 피벗을 하나 선택하고, 작은 것은 왼쪽 부분에, 큰 것은 오른쪽 부분에 넣는 것인데, 정렬이 이미 된 상태에서 최소값이나 최대값을 고르면(피벗) 최악의 경우인 O(n^2)이 나올 수 있다.

---

“평균” 시간복잡도를 구하기 전 가정

• 입력분포(균등분포) 를 가정해야 한다. -> ex) “주사위의 눈이 나올 확률은 모두 1/6로 같다”.
• n개를 정렬한다 했을 때, n개를 모두 나열할 수 있는 경우의 수는 n!가지이다.
• n! 가지가 모두 균등하게 같은 확률로 나온다는 것 을 가정.

---

Basic Operation(기본 연산)

• 기본 연산은 비교 기반의 정렬 로 이루어진다. (정렬의 기본연산이 모두 비교 기반은 아니다.)
• 비교를 하고 난 후, 위치를 바꾸는 행동이나 다른 행동들은 상수시간에 처리한다는 가정.

---

증명

• A(n): n개를 퀵소트로 정렬할 때, “평균적인 비교 횟수”.
• 수식이 많아서 한글 파일로 정리 후 사진을 첨부하였다.

• 위에서 구한 A(n)은 퀵소트 기반의 평균 비교연산 횟수 이다. 우리가 구하고자 했던 것은 퀵소트의 “평균” 시간복잡도 이므로 위의 식을 Big-O로 표현하면 O(nlogn)이 된다.
• 그러므로 퀵소트 기반 “평균” 시간복잡도는 O(nlogn) .