5알고리즘 분석
퀵 정렬의 계산 복잡도는 최악의 경우 선택 정렬이나 삽입 정렬과 같은 O(n2)이지만, 평균적일 때는 병합 정렬과 같은 O(n·logn)입니다.
최악의 경우란 그림 11-2나 11-3과 같이 기준을 잘못 정하여 그룹이 제대로 나뉘지 않았을 때입니다. 하지만 다행히도 좋은 기준 값을 정하는 알고리즘에 관해서는 이미 많이 연구가 되어 있기 때문에 퀵 정렬은 대부분의 경우 O(n·logn)으로 정렬을 마칠 수 있습니다.
5알고리즘 분석
퀵 정렬의 계산 복잡도는 최악의 경우 선택 정렬이나 삽입 정렬과 같은 O(n2)이지만, 평균적일 때는 병합 정렬과 같은 O(n·logn)입니다.
최악의 경우란 그림 11-2나 11-3과 같이 기준을 잘못 정하여 그룹이 제대로 나뉘지 않았을 때입니다. 하지만 다행히도 좋은 기준 값을 정하는 알고리즘에 관해서는 이미 많이 연구가 되어 있기 때문에 퀵 정렬은 대부분의 경우 O(n·logn)으로 정렬을 마칠 수 있습니다.