안녕하세요. 개발자 stark입니다!
이번 포스팅은 알고리즘입니다. 저는 최근 기본기를 다지기 위해 다시 알고리즘을 공부하고 있는데 heap 정렬을 공부하던 중 n개의 숫자를 힙에 삽입하는 시간복잡도가 O(n log n)인 이유가 궁금해서 공부를 했고 이것을 단계별로 설명해 보고자 합니다.
힙 구조 살펴보기
먼저 힙의 구조를 생각해 보겠습니다. 힙은 아래와 같은 완전 이진트리(complete binary tree) 형태를 가지며, 각 노드는 자식 노드들보다 큰 값(최대 힙의 경우)을 가져야 합니다.
100 레벨 0 (루트)
/ \
85 95 레벨 1
/ \ / \
75 80 70 90 레벨 2
/ \ /
50 60 55 레벨 3만약 새로운 원소를 힙에 삽입할 때는 다음과 같은 과정이 일어납니다.
- 우선 새로운 원소를 힙의 마지막 위치(가장 마지막 레벨의 가장 왼쪽 빈자리)에 넣습니다.
- 그다음, 이 원소를 부모 노드와 비교하면서 필요한 경우 위로 올리는 과정(up-heapify)을 수행합니다.
- 이때 중요한 점은 up-heapify 과정에서 새로 삽입된 원소가 이동할 수 있는 최대 거리가 힙의 높이와 같다는 것입니다.
완전 이진트리에서 n개의 노드가 있을 때 트리의 높이는 log n입니다. (위에서 100, 85, 95, 75 이것들이 각각 노드 1개입니다.)
- 높이 1: 최대 2개의 노드
- 높이 2: 최대 4개의 노드
- 높이 3: 최대 8개의 노드
- 높이 h: 최대 2^h개의 노드
따라서 한 원소를 삽입할 때 최악의 경우 log n번의 비교와 교환이 필요합니다.
이제 n개의 원소를 모두 삽입하는 경우를 생각해 보면
- 각각의 원소 삽입에 최대 log n 시간이 걸리고
- 이러한 삽입을 n번 반복해야 하므로
- 전체 시간복잡도는 O(n log n)이 됩니다.
힙정렬의 up-heapify 과정 살펴보기
크기가 8인 힙에 새로운 원소 10을 삽입한다고 가정해 봅시다.
9
/ \
7 8
/ \ / \
5 6 2 1
새로운 원소 10을 마지막에 추가:
9
/ \
7 8
/ \ / \
5 6 2 1
/
10
up-heapify 과정:
9
/ \
7 8
/ \ / \
5 6 2 1
/
10
→
9
/ \
10 8
/ \ / \
5 6 2 1
/
7
→
10
/ \
9 8
/ \ / \
5 6 2 1
/
7이 예시에서 볼 수 있듯이, 새로운 원소는 최대 log n(이 경우 log 8 = 3) 번의 비교와 교환을 통해 올바른 위치를 찾아갑니다.
이진트리의 높이가 log n인 이유
힙은 이진트리이기 때문에, 각 레벨마다 노드의 수가 2배씩 늘어납니다. 이것이 핵심입니다. 예를 들어 16개의 노드가 있는 힙을 그려볼까요?
레벨 0: 16 (2⁰ = 1개 노드)
레벨 1: 15 14 (2¹ = 2개 노드)
레벨 2: 13 12 11 10 (2² = 4개 노드)
레벨 3: 9 8 7 6 5 4 3 2 (2³ = 8개 노드)
레벨 4: 1 (나머지 노드)이 힙에서 중요한 점은 구조가 다음과 같이 구성된다는 것입니다.
- 레벨 0에는 1개의 노드
- 레벨 1에는 2개의 노드
- 레벨 2에는 4개의 노드
- 레벨 3에는 8개의 노드
- 레벨 4에는 남은 노드들이 있습니다.
즉, 각 레벨에서 노드의 개수는 2⁰, 2¹, 2², 2³, 2⁴처럼 2의 거듭제곱으로 증가합니다. 이것이 log n과 관련이 있습니다.
이 관계를 좀 더 자세히 살펴보겠습니다. n이 16일 때를 생각해 보면
- 16 = 2⁴입니다 (2를 4번 곱했다는 의미)
- 따라서 트리의 높이는 4가 됩니다.
- 이를 로그로 표현하면: log₂16 = 4입니다.
이것이 바로 트리의 높이가 log n이 되는 이유입니다. 각 레벨마다 노드의 수가 2배씩 늘어나기 때문에, 노드의 총 개수(n)와 트리의 높이(h)는 2^h = n이라는 관계를 가지게 됩니다. 이 식을 h에 대해 풀면 h = log₂n이 되는 것입니다.
다른 예시로도 이것을 확인해 볼 수 있습니다.
- n = 8일 때: log₂8 = 3 (높이가 3인 트리가 됨)
- n = 32일 때: log₂32 = 5 (높이가 5인 트리가 됨)
- n = 64일 때: log₂64 = 6 (높이가 6인 트리가 됨)
이렇게 노드의 수가 2배씩 늘어나는 구조이기 때문에, 트리의 높이는 항상 노드 수의 로그값이 되는 것입니다.
힙에 새로운 숫자를 추가해 봅시다.
위에서 up-heapify 과정을 살펴봤지만 좀 더 복잡해진 상황에서 새로운 숫자를 힙에 넣을 때를 생각해 봅시다.
새로운 숫자는 항상 마지막 레벨의 가장 왼쪽 빈자리에 들어갑니다. 그리고 이 숫자는 자신의 부모 노드와 비교하면서 필요하다면 위로 올라갑니다. 여기서 중요한 점은 새로운 숫자가 한 번 비교하고 이동할 때마다 한 레벨씩 위로 올라간다는 것입니다. 그렇다면 최악의 경우(새로 넣은 숫자가 계속 위로 올라가야 하는 경우), 몇 번의 비교가 필요할까요? 바로 트리의 높이만큼입니다.
레벨 0: 16 (2⁰ = 1개 노드)
레벨 1: 15 14 (2¹ = 2개 노드)
레벨 2: 13 12 11 10 (2² = 4개 노드)
레벨 3: 9 8 7 6 5 4 3 2 (2³ = 8개 노드)
레벨 4: 1 (나머지 노드)예를 들어 위의 그래프에 숫자 17을 삽입한다고 하면 다음과 같이 동작합니다.
1. 먼저 17은 레벨 4의 다음 빈자리(1 옆)에 들어갑니다.
레벨 0: 16
레벨 1: 15 14
레벨 2: 13 12 11 10
레벨 3: 9 8 7 6 5 4 3 2
레벨 4: 1 172. 17은 자신의 부모 노드(9)와 비교합니다. 17이 더 크므로 9와 위치를 교환합니다.
레벨 0: 16
레벨 1: 15 14
레벨 2: 13 12 11 10
레벨 3: 17 8 7 6 5 4 3 2
레벨 4: 1 93. 다시 새로운 부모 노드(13)와 비교합니다. 17이 더 크므로 13과 위치를 교환합니다.
레벨 0: 16
레벨 1: 15 14
레벨 2: 17 12 11 10
레벨 3: 13 8 7 6 5 4 3 2
레벨 4: 1 94. 다시 새로운 부모 노드(15)와 비교합니다. 17이 더 크므로 15와 위치를 교환합니다.
레벨 0: 16
레벨 1: 17 14
레벨 2: 15 12 11 10
레벨 3: 13 8 7 6 5 4 3 2
레벨 4: 1 95. 마지막으로 루트 노드(16)와 비교합니다. 17이 더 크므로 16과 위치를 교환합니다.
레벨 0: 17
레벨 1: 16 14
레벨 2: 15 12 11 10
레벨 3: 13 8 7 6 5 4 3 2
레벨 4: 1 9이렇게 새로 들어온 숫자는 자신보다 작은 값을 가진 부모를 만나면 계속 위로 올라가게 됩니다. 트리의 높이가 log n이므로, 최악의 경우 이만큼의 비교와 교환이 필요한 것입니다.
마무리하며
오늘 글은 이렇게 마칩니다. 이제부터는 알고리즘을 공부하며 기본 개념들도 조금씩은 정리해볼까 합니다.
최근에 로직을 작성하면서 반복, 정렬 문제가 많아서 어떤 알고리즘을 사용할지 많은 고민을 하게 되었는데요. 이렇게 정리하면서 공부까지 되는 것은 참 블로그 작성의 장점인 것 같습니다.
다들 읽어주셔서 감사합니다 :)