문제
다음 중 최악의 시간 복잡도를 기준으로 나머지 셋과 다른 시간 복잡도를 가지는 정렬은 무엇인가?
① 삽입 정렬 ② 버블 정렬 ③ 선택 정렬 ④ 힙 정렬
정답
4번
해설
정답: 4. 삽입, 버블, 선택 정렬의 최악 시간 복잡도는 O(n²)이고 힙 정렬은 O(n log n)이다.
오답 풀이
- 1번: 삽입 정렬의 최악 시간 복잡도는 O(n²)이다.
- 2번: 버블 정렬의 최악 시간 복잡도는 O(n²)이다.
- 3번: 선택 정렬의 최악 시간 복잡도는 O(n²)이다.
- 4번: 힙 정렬은 최악 시간 복잡도가 O(n log n)이다.
보충 개념 정렬 알고리즘은 평균, 최악, 최선 시간 복잡도를 구분해서 이해해야 한다.