퀵 정렬(3) 퀵 정렬의 시간 복잡도

퀵 정렬의 시간 복잡도

- 퀵 정렬의 평균 시간 복잡도는 O(NlogN) 으로 다른 정렬 알고리즘에 비해 매우 빠른 편이다

- 피벗값의 위치가 변경되어 분할이 일어날 때 마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할한다고 가정해보자

 

 

 

- 데이터의 개수를 8개라고 가정하고, 정확히 절반씩 나누어 간다는 가정을 해보자 

- 이 때 높이를 확인해보면 데이터의 개수가 N 개일 때 높이는 약 logN 이라고 판단할 수 있다

- 즉, 분할이 이루어지는 횟수가 기하급수적으로 감소한다

- 데이터의 개수가 많아질수록 다른 정렬에 비해 압도적으로 빠르게 동작하게 된다

 

---

 

- 다만, 퀵 정렬의 평균 시간 복잡도는 O(NlogN) 이지만, 최악의 경우의 시간 복잡도는 O(N²) 이다

- 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률은 높다

- 반면 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, 이미 어느정도 데이터가 정렬되어 있는 경우는 매우 느리게 동작한다