2017년 3회 정보처리기사 기출문제 15번

15. 힙 정렬에 대한 설명으로 틀린 것은?

    ① 정렬한 입력 레코드들로 힙을 구성하고 가장 큰 키값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬하는 기법이다.

    ② 평균 수행 시간복잡도는 O(nlog2n)이다.

    ③ 입력 자료의 레코드를 완전이진트리(complete binary tree) 로 구성한다.

    ❹ 최악의 수행 시간복잡도는 O(2n4)이다. 

 

300x250

이번 문제는 **힙 정렬(Heap Sort)**의 원리와 시간복잡도에 대한 이해를 묻고 있어요.
하나씩 분석해 보면서 틀린 선택지를 찾아보겠습니다.

---

✅ 힙 정렬(Heap Sort)이란?

• 힙(Heap): 완전이진트리 형태의 우선순위 큐 구조
  • 최대 힙(Max Heap): 루트가 가장 큰 값
  • 최소 힙(Min Heap): 루트가 가장 작은 값

🔧 정렬 방식

1. 입력 데이터를 **힙 구조(완전이진트리)**로 구성
2. 루트 노드(최댓값)를 꺼냄 → 맨 뒤로 보냄
3. 남은 트리에서 다시 힙 구성
4. 이 과정을 반복

---

📊 보기 분석

보기 내용 맞는지 여부 설명

①	힙 구성 후, 루트(최댓값)를 제거하며 정렬	✅ 맞음	힙 정렬의 기본 방식입니다
②	평균 시간복잡도 O(nlog₂n)	✅ 맞음	힙 정렬은 항상 O(nlog n)
③	완전이진트리로 구성	✅ 맞음	힙은 반드시 완전이진트리여야 함
❹	최악 시간복잡도 O(2n⁴)	❌ 틀림 ❗	힙 정렬은 최악도 O(nlog n) 입니다

---

✅ 힙 정렬의 시간복잡도 정리

경우 시간복잡도

최선	O(n log n)
평균	O(n log n)
최악	O(n log n) ✅

즉, **힙 정렬은 항상 O(n log n)**의 성능을 유지합니다.
**O(2n⁴)**는 너무 큰 복잡도로, 틀린 설명입니다.

---

✅ 정답: ❹ 최악의 수행 시간복잡도는 O(2n⁴)이다.

---

🧠 참고: 힙 정렬 특징 요약

항목 내용

구조	완전이진트리 (힙)
정렬 방식	루트 제거 반복
안정 정렬 여부	❌ 불안정 정렬
시간복잡도	항상 O(n log n)
공간복잡도	O(1) (제자리 정렬)

---

시험에서 시간복잡도 관련 보기는 숫자만 다르게 해서 낚시하는 경우가 많으니 조심하세요! 🐟

---

🎯 최종 정답: ❹