2023 spring Algorithm
week03 homework
Problem Set 3
1. Prove that the smallest heighst for any tree on n nodes is Ω(lg n) = -1 + lg(n+1)
n 노드에 있는 트리의 가장 작은 높이는 Ω(lg n) = -1 + lg(n+1) 임을 증명하라.
n개 노드의 가장 작은 트리의 높이가 h이라고 가정해 보자. 이 경우, 각 레벨은 이전 레벨의 리프 노드의 수를 2배로 늘리기 때문에, 이 트리는 적어도 2^h개의 리프 노드를 가지고 있어야 한다. 또한, 이진 트리에서 각 내부 노드는 리프 노드보다 1개 적기 때문에, 트리의 전체 노드 수는 리프 노드의 수와 내부 노드의 수(리프 노드 수보다 1개 작음)의 합입니다.
따라서
n >= 2^h + (2^h - 1)
이고, 이를 간단하게 정리하면 아래와 같다.
n >= 2^(h+1) - 1
양변에 로그를 취하면 다음과 같다
log(n+1) >= h+1
h <= log(n+1) - 1
h = O(log n)
따라서, 우리는 어떤 n개 노드의 가장 작은 트리의 높이가 O(log n)임을 보여 주었습니다. 하지만, 하한을 증명하기 위해서는 완전 이진 트리를 예로 들 수 있습니다. 높이가 h인 완전 이진 트리는 2^h개의 리프 노드와 2^(h+1)-1개의 총 노드를 가집니다. 따라서 다음이 성립합니다:
n = 2^(h+1) - 1
양변에 로그를 취하면 다음과 같다.
log(n+1) = h+1
h = log(n+1) - 1
따라서, 어떤 n개 노드의 가장 작은 트리의 높이가 최소 log(n+1) - 1 = Ω(log n)이며, 이는 Ω(log(n))과 동일하다.
2. When you shrink the space of direct access arrays, you might want to use a linked list data structure. What would be the problem if you use the linked list? Show your answer with explaining the time complexity.
배열을 축소할 때 연결 리스트 자료구조를 이용했을 때의 문제점은?
시간복잡도를 이용해 설명하라.
연결 리스트를 사용하면 특정 인덱스의 요소에 접근하려면 처음부터 리스트를 순회해야 하므로 시간 복잡도는 O(n) 이다. 반면, 직접 접근 배열은 요소에 직접 접근할 수 있으므로 시간 복잡도가 O(1)이다. 따라서, 직접 접근 배열에 비해 연결 리스트는 시간적인 측면에서 문제점을 보일 수 있다.
## 3.
4. Birthday Data Set
4-1. Put them into your unordered array using set.
4-2. Put them into the sorted array set.
4-3. Put them into the direct access array set.
4-5. Compare their size.
4-6. Compare their interfaces: build, find, insert, delete, find_min, find_max, find_next, find_prev.
birthday data set은 잘 모르겠습니다.
