[자료구조] 힙정렬(HeapSort) 시간복잡도

시간복잡도를 구하는 점화식을 계산하기 전에
완전이진트리의 depth와 비교연산횟수의 관계부터 알아야한다.

결정트리에서 leaf 에 도달할 때까지의 비교 횟수의 최댓값은 depth와 같다.

여기서 비교횟수의 "최대값" 이라고 하는 이유는 

시간복잡도는 최악의 상황을 계산하는 것이기 때문 ㅇㅇ

그리고 여기서 depth는 log2n에 가우스 함수 씌운 것이다.

예를 들어 만약 10번째 노드가 추가되었다면
이 노드를 정렬하기 위해 필요한 비교연산 개수는
[ log2(10) ] 즉 3번의 비교연산만 추가되면 된다는 것이다!

 

위 그림을 참고하면 

10번이 추가되면 5번 2번 1번

이렇게 세 번의 비교연산을 

해야하는 경우가 최악의 경우이다!