[알고리즘 깨알팁] heapify 시간복잡도 계산

바쁘신분은 3번만

 

나중에 그림 첨부 요망

1. heapify란?

heapify는 일반 배열을 heap 자료구조로 만드는 과정.

 

2. 시간복잡도 계산

heap에서 left child는 현재 인덱스 *2, right child는 현재 인덱스 *2 +1 이다.

즉, 루트(인덱스 번호 1)에서 현재 힙의 최대 사이즈 / 2 노드까지만 자식 노드가 존재한다.

-> 현재 배열의 중앙부터 루트까지 heapify를 완성해 나가면 heap 자료구조를 만들 수 있다.

 

여기서, 노드의 중앙 부터 heapify가 일어나는 수를 최악으로 계산하면,

heapify 과정을 트리의 높이 h - 현재 자신의 depth 번 하게된다.

 

노드의 중앙 부터 했으므로, 노드의 중앙은 높이가 h-1, 노드의 개수는 n/2개이다.

즉, 해당 노드들은 heapify를 최대 한번씩만 한다. (총 n/2*(h-(h-1)) = n/2번

다음은 높이 h-2가 n/4개의 노드를 가지고있다. heapify 횟수는 (n/4*(h-(h-2)) = n/4*2번.

다음은 높이 h-3가 n/8개의 노드를 가지고있다. heapify 횟수는 (n/8*(h-(h-3)) = n/8*3번.

...

다음은 높이 h-i가 n/(2^i)개의 노드를 가지고있다. heapify 횟수는 (n/(2^i)*(h-(h-i)) = n/(2^i)*i번.

 

결국 heapify 시간복잡도는 i/(2^i)를 1~h 까지 sum한 후에 n을 곱하면 된다.

이를 무한대로 발산시키고 합을 S라고 하면,

 

2S = (1 +   2/2 + 3/4 + 4/8 + ...)*n

S =  (       1/2 + 2/4 + 3/8 + ...)*n

S = (1 +    1/2 + 1/4 + 1/8 + ... )*n

 

S = 1 / (1-1/2)*n = 2n

따라서 위의 무한 수열을 풀면 결국 S 값은 2n이 된다.

 

즉, 어떤 배열의 heapify의 시간복잡도는 O(n)이다.

 

heapify 설명 : ordo.tistory.com/88

무한 수열 풀이: www.quora.com/How-do-you-evaluate-the-sum-of-n-2-n-from-n-1-to-infinity

 

3. 결론

일반전인 배열을 모두 heapify하는 과정의 시간복잡도는 O(n)이다.