[알고리즘] Quick sort는 왜 빠를까? (3) : 비교 실행의 개수 계산

비교의 수 가 곧 시간이다

전 게시물까지 내린 결론은

퀵 소트의 실행 시간은 서로 다른 두 원소가 얼마나 직접적으로 비교가 되느냐에 직결된다는 것이었다.

퀵 소트의 피벗은 랜덤으로 결정된다고 가정하였으므로,

랜덤 피벗에 따라 서로 다른 두 원소가 얼마나 비교되는지가 결정된다!

---

비교될 확률

비교되는 정도의 기대값 (결론을 식으로 표현한 경우)

i~j 까지 원소들 Z_ij 가 있을 때 원소 , z_i 와 z_j 가 비교될 확률을 구해보자.

만약 피벗이 i < p < j 인 p로 설정이 된다면,

i 와 j 는 p 랑만 비교가 된 후 서로 다른 두 하위문제로 넘어가는 경우이다.

따라서 피벗이 i 혹은 j 로 설정 돼었을 때 X_ij = 1 이다.

따라서  Pr{z_i is compared to zj} = 2 / j-i+1 (i~j 까지의 개수)  이다.

 

최종 비교시간 계산

이를 이제 식으로 계산해보면 다음과 같은 결과를 얻을 수 있다.

따라서, Quicksort 의 실질적인 기대시간은 O(n2) 가 아니라 O(nlgn) 이라 생각해도 되는 것이다!!

 

* 뿐만아니라 Quicksort는 메모리적인 측면에서도 강점을 가진다.

 

 

* 참고 : 고려대학교 정순영 교수님 알고리즘 강의