Problem Set 3

Considering the progress of the class, a few homework problems have been excluded.

 

Read Chapter 8.

 

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.

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.

 

 

1. n개의 노드에서 트리의 가장 작은 높이가 Ω(lg n) = - 1 + lg(n+1)임을 증명하라.

 

귀납법을 이용하여 증명해보자

1) base case (n=1인 경우)

n = 1인 경우, 트리의 높이는 0이고 -1 + lg(n+1) = 0이므로 성립한다.

 

2) n = k인 경우 성립한다고 가정하자

n = k인 경우, 트리의 가장 작은 높이의 시간 복잡도는 Ω(lg k) = - 1 + lg(k+1)임을 가정한다.

 

3) n = k+1

k개의 노드를 가진 트리에서 1개의 노드를 추가하여 k+1개의 노드를 가진 트리를 만들 때, 트리의 높이는 적어도 1개 증가한다.  그러면 새로운 트리의 가장 작은 높이의 시간 복잡도는 Ω(lg (k+1)) = - 1 + lg((k+1)+1) 이 된다. n = k+1인 경우에도, n = k인 경우와 똑같은 형태의 식이 성립한다. 

 

→ 따라서 n개의 노드에서 트리의 가장 작은 높이의 시간복잡도는 Ω(lg n) = - 1 + lg(n+1)이다.

 

 

2. 직접 액세스 배열의 공간을 축소할 때 연결된 목록 데이터 구조를 사용할 수 있습니다. 연결 리스트를 사용한다면 어떤 문제가 생길까요? 시간복잡도를 설명하면서 답을 보여주세요.

 

 

직접 배열 연산은 바로 인덱스에 접근할 수 있다. 하지만, 연결리스트로 구현하게 되면 바로 인덱스에 접근할 수 없어 시작점부터 시작하여 내가 찾는 인덱스까지 순회해야한다. 최악의 경우, 연결리스트의 시간복잡도가 직접배열연산보다 나빠진다. 직접배열연산은 O(1)의 시간 복잡도가 발생하는 반면, 연결리스트는 O(n)의 시간복잡도가 필요하다. 

 

[chat GPT]

직접 액세스 배열의 공간을 축소할 때 링크드 리스트 데이터 구조를 사용하고 싶을 수 있습니다. 그러나 링크드 리스트를 사용할 경우 발생하는 문제와 그에 따른 시간 복잡도에 대해 설명해드리겠습니다.

링크드 리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성되는 데이터 구조입니다. 각 노드는 동적으로 할당되며 메모리에서 연속된 위치에 저장되지 않습니다. 이러한 특징으로 인해 링크드 리스트에는 몇 가지 문제가 발생할 수 있습니다.

1. 직접 액세스가 불가능한 구조: 링크드 리스트에서는 특정 인덱스로 직접 액세스하는 것이 불가능합니다. 특정 노드에 액세스하려면 리스트의 첫 번째 노드부터 순차적으로 탐색해야 합니다. 이는 인덱스로 노드에 액세스하는 배열에 비해 시간이 더 많이 소요될 수 있습니다.
2. 메모리 오버헤드: 링크드 리스트는 각 노드마다 포인터를 저장해야 하므로 메모리 오버헤드가 발생합니다. 각 노드마다 추가적인 공간이 필요하며, 링크드 리스트의 크기가 커질수록 메모리 사용량이 증가합니다.
3. 순차 액세스의 비효율성: 링크드 리스트는 포인터를 통해 다음 노드로 이동해야 하므로, 순차적으로 데이터에 액세스할 때에도 각 노드를 따라 이동해야 합니다. 이는 캐시의 지역성을 활용하지 못하고 메모리 액세스 비용을 증가시킬 수 있습니다.

따라서 링크드 리스트를 사용하면 직접 액세스가 불가능하고 메모리 오버헤드가 발생하며, 순차 액세스에서 비효율적일 수 있습니다. 이러한 문제로 인해 시간 복잡도도 영향을 받게 됩니다. 링크드 리스트의 탐색, 삽입, 삭제 작업은 최악의 경우 O(n)의 시간 복잡도를 가질 수 있습니다. 링크드 리스트의 길이가 길어질수록 이러한 작업의 시간이 더 많이 소요됩니다.

이와는 달리 직접 액세스 배열은 O(1)의 시간 복잡도로 특정 인덱스에 직접 액세스할 수 있고, 캐시의 지역성을 활용하여 효율적인 액세스가 가능합니다. 따라서 직접 액세스가 필요한 경우 링크드 리스트보다는 직접 액세스 배열을 사용하는 것이 더 효율적일 수 있습니다.

 

 

 

 

 

4. 생일데이터를 이용하여 다음의 문제들을 풀어라

 

 

4-1. 세트를 사용하여 정렬되지 않은 배열에 넣어라.

 

 

import pandas as pd

df = pd.read_csv('/Users/Projects/Birthday.csv', encoding='UTF-8')
birth_df = df.iloc[1:, 2:3]
birth_df.fillna(0)
_birth_lst = birth_df.values.tolist()
birth_lst = []
for i in range(0, len(_birth_lst)):
   birth_lst.append(float(_birth_lst[i][0]))
   
print(birth_lst)

 

 

4-2. 정렬된 배열 집합에 넣어라.

 

import pandas as pd

df = pd.read_csv('/Users/Projects/Birthday.csv', encoding='UTF-8')
birth_df = df.iloc[1:, 2:3]
birth_df.fillna(0)
_birth_lst = birth_df.values.tolist()
birth_lst = []
for i in range(0, len(_birth_lst)):
    birth_lst.append(float(_birth_lst[i][0])
    
print(sorted(birth_lst))

 

 

4-3. 직접 배열에 넣어라.

 

잘 모르겠다.

 

 

 

4-5. 크기를 비교해라.

 

 

unordered array, sorted array,  direct access array 모두 크기는 100이 나온다.

 

 

 

4-6.  인터페이스를 비교해라. (build, find, insert, delete, find_min, find_max, find_next, find_prev)

 

강의자료 참고