← 회차 전체 문제

공개 기출자동 검사 완료2022년 국가직 기출 · 컴퓨터일반 · 자료구조·알고리즘 · 2번

정렬 알고리즘 중 최악의 경우를 가정할 때 시간복잡도가 다른 것은?

1
삽입 정렬(Insertion sort)
오답 이유삽입 정렬은 역순 입력에서 각 원소가 앞의 거의 모든 원소와 비교·이동되어 O(n²)이다.
2
쉘 정렬(Shell sort)
오답 이유시험에서 전제하는 기본 간격 감소 방식의 쉘 정렬은 최악에 O(n²)까지 갈 수 있다.
3
버블 정렬(Bubble sort)
오답 이유버블 정렬은 역순 입력에서 인접 비교를 약 n(n-1)/2회 수행해 O(n²)이다.
4
힙 정렬(Heap sort)
정답 근거힙 구성과 n번의 삭제·재정렬이 각각 로그 높이 안에서 처리되어 최악에도 O(n log n)이다.

정답·상세해설

정답 4번

정렬 알고리즘의 최악의 경우 시간복잡도를 비교하는 문제입니다. 힙 정렬은 최악의 경우에도 n log n의 시간복잡도를 보장하 여 다른 알고리즘들과 차이가 납니다. 삽입 정렬, 쉘 정렬, 버블 정렬: 최악의 경우 N^2의 시간복잡도를 가짐

콘텐츠 기록

콘텐츠 정보

자료 유형: 공개 기출
검수 상태: 자동 검사 완료
해설 작성·검수: 정처LAB 자동 검사
최종 검수: 자동 검사 완료

이 번호부터 전체 회차 풀기 내 오답 복습 회차 전체보기 시험별 CBT 안내