문제
다음 중 평균 시간 복잡도가 O(N²)이 아닌 정렬 방법은?
① 선택 정렬(Selection Sort) ② 버블 정렬(Bubble Sort) ③ 삽입 정렬(Insertion Sort) ④ 퀵 정렬(Quick Sort)
정답
4번
해설
정답: 4. 퀵 정렬의 평균 시간 복잡도는 O(n log n)이다.
오답 풀이
- 1번: 선택 정렬의 평균 시간 복잡도는 O(n²)이다.
- 2번: 버블 정렬의 평균 시간 복잡도는 O(n²)이다.
- 3번: 삽입 정렬의 평균 시간 복잡도는 O(n²)이다.
- 4번: 퀵 정렬의 평균 시간 복잡도는 O(n log n)이다.
보충 개념 퀵 정렬은 최악의 경우 O(n²)까지 떨어지지만, 평균적으로는 O(n log n)의 성능을 보인다.