[자료구조](-)[힙 생성의 시간복잡도는 O(n)?]

트리가 complete binary tree이므로
N개의 노드가 있을 때
    주어진 트리의 최대 높이 H = logN
    높이가 h인 부분 트리의 개수 = $\lceil{\frac{n}{2^{h+1}}}\rceil$

 

이때 bubbling down이므로 leaf는 계산하지 않는다.

(왜냐하면 가장 마지막 부모 노드부터 시작하니까)
즉, 높이 h = 0인 노드는 무시하고 시간복잡도를 계산해야 한다.
높이가 h인 노드에서 bubbling down으로 내려갈 때 연산은 최대 h번 한다고 할 수 있다.
(leaf에선 높이도 0이고 연산도 0번)
따라서 bubbling down의 시간복잡도 = O(h)

 

이제 모든 h에 대해 계산하면
$$ 시간복잡도 = O( \sum_{h=0}^{logN}\lceil{\frac{n}{2^{h+1}}}\rceil \times h ) $$
이때 big-O는 매우 큰 N에 대해서 유의미하므로 N을 무한으로 보내고
천장 함수도 적당히 무시해주면,
$$O(n \times \sum_{h=0}^{\infty}{ \frac{h}{2^{h+1}}})$$
$\lim_{h \to \infty} \frac{h}{2^{h+1}} = 0$ 이므로, $\sum_{h=0}^{\infty}{ \frac{h}{2^{h+1}}}$는 상수로 수렴하니 무시하면
결국 시간복잡도 = O(n)이 된다.