2022 국가직9급 컴퓨터일반 2번 해설 — 정렬 시간복잡도
정답 ④번출제 쟁점 정렬 시간복잡도발문 옳은 것 고르기
문제
정렬 알고리즘 중 최악의 경우를 가정할 때 시간복잡 도가 다른 것은?
- ① 삽입 정렬(Insertion sort)
- ② 쉘 정렬(Shell sort)
- ③ 버블 정렬(Bubble sort)
- ④ 힙 정렬(Heap sort) 알고리즘 최선 평균 최악 삽입 정렬 O(n) O(n2) O(n2) 선택 정렬 O(n2) O(n2) O(n2) 버블 정렬 O(n2) O(n2) O(n2) 셀 정렬 O(n) O(n1.5) O(n2) 퀵 정렬 O(nlog2n) O(nlog2n) O(n2) 힙 정렬 O(nlog2n) O(nlog2n) O(nlog2n) 합병 정렬 O(nlog2n) O(nlog2n) O(nlog2n) 기수 정렬 O(dn) O(dn) O(dn) ← 정답
선지별 해설
① 삽입 정렬(Insertion sort)
이 선지 진술은 틀림(X)
삽입 정렬은 최악의 경우 O(n^2) 시간이 걸린다. 보기 중 최악 시간복잡도가 다른 것은 O(n log n)을 보장하는 힙 정렬이다.
② 쉘 정렬(Shell sort)
이 선지 진술은 틀림(X)
교재식 비교에서 셸 정렬은 최악 O(n^2)로 제시되는 경우가 많다. 보기 중 최악 시간복잡도가 다른 것은 힙 정렬이다.
③ 버블 정렬(Bubble sort)
이 선지 진술은 틀림(X)
버블 정렬은 최악의 경우 O(n^2) 시간이 걸린다. 보기 중 최악 시간복잡도가 다른 것은 O(n log n)의 힙 정렬이다.
④ 힙 정렬(Heap sort) 알고리즘 최선 평균 최악 삽입 정렬 O(n) O(n2) O(n2) 선택 정렬 O(n2) O(n2) O(n2) 버블 정렬 O(n2) O(n2) O(n2) 셀 정렬 O(n) O(n1.5) O(n2) 퀵 정렬 O(nlog2n) O(nlog2n) O(n2) 힙 정렬 O(nlog2n) O(nlog2n) O(nlog2n) 합병 정렬 O(nlog2n) O(nlog2n) O(nlog2n) 기수 정렬 O(dn) O(dn) O(dn)
이 선지 진술은 옳음(O)
힙 정렬은 힙 구성과 반복 삭제를 통해 최선·평균·최악 모두 O(n log n)으로 동작한다. 그래서 보기 중 최악 복잡도가 다른 정렬이다.
핵심 요약 (Q&A)
- Q. 2022 국가직9급 컴퓨터일반 2번의 핵심 쟁점은 무엇인가?
- A. 2022 국가직9급 컴퓨터일반 2번은 정렬 시간복잡도에 관한 문항으로, "옳은 것"을 고르는 문제입니다.
- Q. 2022 국가직9급 컴퓨터일반 2번의 정답은?
- A. 정답은 ④번입니다. 힙 정렬은 힙 구성과 반복 삭제를 통해 최선·평균·최악 모두 O(n log n)으로 동작한다. 그래서 보기 중 최악 복잡도가 다른 정렬이다.