Read Chapter 8.
1. Prove that the smallest height for any tree on n nodes is Ω(lg n) = - 1 + lg(n+1).
먼저, n개의 노드를 가지는 트리의 가장 낮은 높이의 시간복잡도가 Ω(lg n) = - 1 + lg(n+1)이라고 가정하자.
Base Case 를 구하면, 즉 n = 1일 경우 단일노드로 구성되며 높이는 1이다. 따라서, -1 + lg(2)이기 때문에 시간복잡도는 0이 된다.
귀납적 추론을 이용해 노드가 n일때 가장 낮은 높이를 구해야한다. 노드의 수는 n 개일때, T1이 왼쪽 서브트리 (k개) , T2가 오른쪽 서브트리 (n-k)개 노드라고 둘 수 있다. 전체 노드의 높이를 구하려면 h(T) >= h(T1) + h(T2) + 1 라고 할 수 있다. h(T1) = -1 + lg(k+1)이고 h(T2)는 lg(n-k+1)이다. 따라서, h(T1) + h(T2)는 약 lg(n+1)이다. h(T) = lg(n+1) + 1이다. 즉 이는 Ω(lg n)이며, n 노드에 있는 트리의 가장 작은 높이가 n에 대한 유도에 의해 Ω(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.
배열의 크기를 줄였을때, 링크드리스트가 더 낮은 성능을 나타낼 수 있다. 먼저 Random access 의 경우의 시간복잡도가 배열의 경우 O(1)이지만 linked list 의 경우 최악의 경우 모두를 탐색해야하는 O(n)이 될 수 있다. 또한 삽입 삭제의 경우 해당 target의 위치를 알아야 하기 때문에 O(n)이다. 하지만 linked list는 포인터만 저장하면 되기에 메모리 크기에 있어 장점이 있다.
4. Use the birthday dataset, Do the followings:
4.1. Put them into your unordered array using set.
import csv
b = []
f = open('BirthdayData.csv','r')
rdr = csv.reader(f)
for line in rdr:
b.append(line[0])
print(b)
f.close()answer = ['05,31']
def find(S):
for i in range(100):
if(S == b[i]):
return i+1
find(answer)
len(b)생일 데이터 집합중 가장 마지막 값인 5월 31일을 find 할 경우, 100을 출력한다. 따라서 정렬되지 않은 배열에서는 집합의 길이 만큼 시간 복잡도(O(n))를 가지는 것을 알 수 있다. 정렬되지 않은 배열에서 insert와 delete, find_mix, max, find_next, prev 의 시간 복잡도는 O(n)이다.
4.2. Put them into the sorted array set.
def prefix_max(A, i):
if i>0:
j = prefix_max(A, i-1)
if A[i] < A[j]:
return j
return i
def selection_sort (A, i = None):
if i is None: i = len(A) - 1
j = prefix_max(A,i)
A[i], A[j] = A[j], A[i]
selection_sort(A, i-1)이는 선택정렬을 이용해 정렬된 데이터이다. 선택 정렬은 가장 작은 수는 앞으로 젤 큰 수는 뒤로 가는 방식이다. 이를 하기 위해 우리는 하나의 element를 다 비교해봐야한다. 따라서 O(n*2)이라는 시간복잡도가 나온다.
정렬을 했을 경우 find의 시간 복잡도는 O(lgN)을 가진다. insert와 delete는 O(n)이고, max와 min은 O(1), next와 prev는 lgN이다.
4.3. Put them into the direct access array set
해당 질문에 대한 코드를 어떻게 짜야할지 잘 모르겠다. direct access 는 해당 키에 대해 바로 접근이 가능하기 때문에 O(1) 시간 복잡도가 나온다.
4.5. Compare their size.
|
Unordered Array Set
|
Sorted Array Set
|
Direct Access Array Set
|
|
100
|
100
|
100
|
4.6. Compare their interfaces: build, find, insert, delete, find_min, find_max, find_next, find_prev.
Array Set
|
Container
|
Static
|
Dynamic
|
Order
|
Order
|
|
build(A)
|
find(A)
|
insert(A)
delete(A)
|
find_min()
find_max()
|
find_next()
find_prev()
|
|
n
|
n
|
n
|
n
|
n
|
Sorted Array Set
|
Container
|
Static
|
Dynamic
|
Order
|
Order
|
|
build(A)
|
find(A)
|
insert(A)
delete(A)
|
find_min()
find_max()
|
find_next()
find_prev()
|
|
O(nlogn)
|
logn
|
O(n)
|
1
|
logn
|
Direct Access Array Set
|
Container
|
Static
|
Dynamic
|
Order
|
Order
|
|
build(A)
|
find(A)
|
insert(A)
delete(A)
|
find_min()
find_max()
|
find_next()
find_prev()
|
|
O(n)
|
O(1)
|
O(1)
|
O(n)
|
O(n)
|