들어가기 전에

퀵 정렬에서 최악의 경우가 발생했을 때의 시간 복잡도에 대해 살펴보도록 하겠습니다.

학습 목표

퀵 정렬에서 최악의 경우가 발생했을 때의 시간 복잡도를 설명할 수 있습니다.

핵심 단어

• 퀵 정렬
• 시간 복잡도

강의 듣기

(원본 파일의 문제로 2분 15초부터 검은 화면이 나옵니다. 퀵 정렬에서의 최악의 경우에 대한 설명은 그 전에 끝나기 때문에 학습에 큰 영향은 없지만, 퀵 정렬에 대해 더 알고싶으시면 아래 참고자료의 블로그에서 확인하실 수 있습니다.)

퀵 정렬 (최악의 케이스)

퀵 정렬에서는 전체 데이터를 계속해서 반으로 줄여나가기 때문에 평균적인 상황에서는 O( $nlogn$ )의 시간 복잡도를 갖습니다. 하지만 최악의 경우, 계속해서 최소인 지점을 중심점으로 잡는다면 시간 복잡도는 O( n^2  n​2​​ )까지도 늘어날 수 있습다. (모든 숫자가 중심점보다 커서 대소비교만 하고 분류가 되지 않는 경우입니다.)

생각해보기

1) n개의 숫자가 있는 리스트에 퀵 정렬을 적용하려 합니다. 최악의 경우에는 총 몇 번의 대소 비교를 해야 하나요?

참고자료