힙 정렬(Heapsort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
이진 트리를 최대 힙으로 만들기 위하여 최대 힙으로 재구성 하는 과정이 트리의 깊이 만큼 이루어 지므로 O(log n) 의 수행시간이 걸린다. 구성된 최대 힙으로 힙 정렬을 수행하는데 걸리는 전체시간은 힙 구성시간과 n개의 데이터 삭제 및 재구성 시간을 포함한다
즉, 힙 정렬의 시간복잡도는 O(n log n)이 된다. 힙 정렬은 트리구조를 이용하기 때문에 전체 높이가 O(log n)이다. 따라서, 하나의 요소를 heap에 삽입하거나, 삭제할 때 heap을 재구성하는 시간은 O(log n) 만큼 소요된다. 요소의 개수가 n개이므로 전체적으로 걸리는 시간은 O(n log n)이 된다. Heap Sort가 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라, 가장 큰 값 몇개만 필요할 때 이다.
[단점]
시간 복잡도(Time Complexity) 는 O(n log n) 이다.
- 시간 복잡도(Time Complexity) : 알고리즘의 수행시간 분석 결과
expected worst-case time complexity is O(N)
- 공간 복잡도(Space Complexity) : 알고리즘의 메모리 사용량에 대한 분석 결과
expected worst-case space complexity is O(N)
http://ledgku.tistory.com/33
빅오(O)의 복잡도
O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n) < O(n!) |
복잡도가 증가 할 수록 연산횟수가 많아지므로, 성능이 떨어지게 된다.