1. Prove that the smallest height for any tree on n nodes is Ω(lg n) = - 1 + lg(n+1).
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)의 시간이 걸리며 포인터의 사용으로 인해 저장공간이 낭비된다는 문제점이 있다.
ArrayList 와 LinkedList의 시간복잡도 비교는 다음과 같다.
4. Use the birthday dataset, Do the followings:
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.
인터페이스 시간복잡도 비교는 다음과 같다.
정렬되지 않은 배열은 n의 시간복잡도를 가진다.
정렬배열에서 build는 nlgn, find, find_next, find_prev는 lgn, insert, delete는 정렬되지않은 배열과 마찬가지로 n의 시간복잡도를 가진다. min, max값은 정렬되어있는 배열에서는 맨 앞과 맨 뒤에 위치하기 때문에 시간복잡도 1을 갖는다.
