computational complexity : The Sorting Problem(2)

HeapSort

Heap: 각 노드의 값이 자식보다 크거나 같은 complete binary tree

 

 

 

 

어떻게 초기 힙을 구성할까?

1. 배열구성

2. 마지막 level서부터 올라가며 힙 만들기

이미 힙이다.

루트 노드보다 자식 노드가 크다면 자식 노드 중 가장 큰 값이 루트 노드로 올라가도록

 

 

 

 

 

 

어떻게 힙을 유지하며 루트 key를 제거할까?

1. 루트를 삭제한 후에 마지막 키를 루트로 올려준다.
2. 루트가 된 키를 힙이 될 때까지 아래로 내려준다.

 

 

<HeapSort의 수도코드>

 

 

 

 

Worst Case Time Complexity of HeapSort

Basic Operation: siftDown에서 키의 값 비교

Input Size: n(키의 개수)

 

 

n= 2^d라고 가정

(d는 마지막 깊이의 값)

1. makeHeap에서의 siftDown

-> shiftDown의 비교횟수를 계산할 때 마지막 레벨 d에서의 노드 1개는 무시하고 계산한다.
그 다음 마지막 결과에 무시했던 노드를 추가한다.

 

 

마지막 무시했던 d를 더하면 

->

d는 상수이므로 2^d-1는 선형시간 걸림

 

 

2. removeKeys에서의 siftDown

-> 마지막 레벨 d에서의 노드를 무시하지 않고 계산

 2^(d-1)개의 키들을 제거하고, 각각이 새로운 top 노드가 되도록 하는

최악의 경우 각각이 d-1번의 sift가 발생한다.

-> 2^d-1개의 키들을 sift하는 횟수 

=(d-1) * 2^(d-1)

 

 2^(d-2)개의 키들을 제거하고, 각각이 새로운 top 노드가 되도록 하는

최악의 경우 각각이 d-2번의 sift가 발생한다.

-> 2^d-2개의 키들을 sift하는 횟수 

=(d-2) * 2^(d-2)

 

 

따라서 모든 레벨에서 고려해보면

그러므로 HeapSort의 Worst Case 시간복잡도는

-> nlgn - n +1

 

 

 

 

 

Decision Trees for Sorting Algorithms

 

 

 

 

 

* Lemma 1. 

n개의 서로 다른 key를 정렬하는 모든 알고리즘에는 정확히 n!개의 leaves를 포함하는 가지치기 가능하고,

유효한 바이너리 decision tree가 해당된다.

 

Lemma 2.

worst case 비교 횟수는 decision tree의 해당 depth와 동일하다.

 

Lemma 3.

바이너리 트리의 leaf의 개수가 m이라 하고 d를 leaf의 깊이라 하면

d >= lg m의 올림값

 

-> Theorem 1.

worst case 비교횟수는 적어도 lg(n!)의 올림값이다.

 

Lemma 4.

양수 n에 대하여 lg(n!) ≥ n lgn–1.45n.

 

-> Theorem 2.

worst case 비교횟수는 적어도  n lgn–1.45n의 올림값이다.