문제
정렬 알고리즘 중 평균 시간 복잡도가 O(n log n)이 아닌 것은?
① 퀵 정렬 ② 병합 정렬 ③ 힙 정렬 ④ 거품 정렬
정답
4번
해설
정답: 4. 거품 정렬의 평균 시간 복잡도는 O(n²)이다.
오답 풀이
- 1번: 퀵 정렬의 평균 시간 복잡도는 O(n log n)이다.
- 2번: 병합 정렬의 시간 복잡도는 O(n log n)이다.
- 3번: 힙 정렬의 시간 복잡도는 O(n log n)이다.
- 4번: 거품 정렬은 평균 O(n²)이다.
보충 개념 버블, 선택, 삽입 같은 단순 정렬은 일반적으로 O(n²)에 해당한다.