티스토리 뷰
처음 배열에서 힙을 구성할 때 선형시간으로 구성하는 방법이 있다. 일반적으로 각각의 원소를 삽입하는 방식으로 힙을 구성하면 자명하게 $O(N \lg N)$ 시간복잡도를 갖는다. 이를 $O(N)$에 해결할 수 있는 방법을 설명하겠다.
힙의 모양을 구성한 뒤에 맨 아래 정점부터 처리하는데, 부모 정점의 값보다 자신의 값이 우선순위가 더 높다면 부모 정점의 값과 자신의 값을 바꾼다. 이 뒤에 자신의 값의 우선순위가 자기 자식 정점의 값보다 낮을 수 있으므로 마찬가지로 재귀적으로 확인해준다. 이렇게 진행될 경우 아래에서 $h$ 높이에 있는 정점을 처리할 때, 최대 $h$번의 swap이 일어날 수 있다. 이를 수식으로 써서 나타내면 연산회수의 상한은 $n \times \sum{\frac{h}{2^{h-1}}}$ 이다.
$\sum{\frac{h}{2^{h-1}}} = 1 + \frac{2}{2} + \frac{3}{4} + \frac{4}{8} + \frac{5}{16} + \frac{6}{32} + \dots = (1 + \frac{1}{2} + \frac{1}{4} + \dots) + \frac{1}{2}\times(1+\frac{1}{2}+\frac{1}{4}+\dots)+\dots$
$1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots = 2$ 이므로 $\sum{\frac{h}{2^{h-1}}} = 4$ 가 된다. 따라서 위 방식으로 힙을 구성할 시 전체시간복잡도가 $O(N)$이 되는 것을 알 수 있다.
'공부' 카테고리의 다른 글
Convex Hull Optimization (4) | 2016.08.23 |
---|---|
가장 먼 두 점 구하기 (6) | 2016.07.17 |
String Matching Algorithms (5) | 2016.06.24 |
Persistent Segment Tree (6) | 2016.06.23 |
Divide & Conquer Optimization (3) | 2016.06.23 |
- Total
- Today
- Yesterday
- IOI2013
- vote
- Knuth Optimization
- IOI2011
- ioi
- Algorithm
- Splay Tree
- BOI 2001
- Boyer
- IOI2014
- moore
- majority
- IOI2012
- USACO
- Boyer-Moore Majority Vote Algorithm
- dynamic programming
- Segment tree
- BOI 2009
- Tree
- BOI
- Dynamic Pramming
- HackerRank
- TRIE
- z-trening
- optimization
- Dijkstra
- Parametric Search
- idea
- Divide & Conquer
- Greedy Method
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |