힙 정렬(Heap Sort)에 대한 설명으로 틀린것은? | 21년-2회차-정보처리기사-필기 기출문제 상세 페이지
121년-2회차-정보처리기사-필기
힙 정렬(Heap Sort)에 대한 설명으로 틀린것은?
1
정렬할 입력 레코드들로 힙을 구성하고 가장 큰 키 값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬하는 기법이다.
2
평균 수행 시간은 O(nlog2n)이다.
3
완전 이진트리(complete binary tree)로 입력자료의 레코드를 구성한다.
4
최악의 수행 시간은 O(2n4)이다.
해설
힙 정렬(Heap Sort)은 완전 이진트리 형태의 힙을 구성한 뒤 가장 큰(또는 작은) 키를 가진 루트 노드를 반복적으로 제거·재구성하며 정렬하는 기법으로, 힙 재구성에 O(log n)이 걸리는 과정을 n번 반복하므로 최선·평균·최악 모두 O(n log n)이다.
따라서 최악의 수행 시간이 O(2n4)라는 표현은 힙 정렬의 시간복잡도와 무관한 잘못된 진술이다.
내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.