Sorting (2)

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

• 트리의 기본적인 특징
  : n개의 노드를 가진 트리는 n-1개의 간선을 갖는다.
  : 높이가 h인 이진트리가 가질 수 있는 최대 노드 개수는 2^(h+1)-1
• 모든 레벨에 노드가 완전히 차있게 하여 높이를 가장 작게 만들기 위해서는 가장 많은 노드 개수를 가져야 한다.
• n <= 2^(h+1)-1
  n + 1 <= 2^(h+1)
  log(n+1) <= h + 1
  -1 + log(n+1) <= h
  -> Ω(log n) = - 1 + log(n+1)

2. direct access arrays의 공간을 축소할 때 linked list 자료구조를 사용할 수 있습니다. linked list를 사용할 경우 발생할 문제를 시간 복잡성과 함께 설명하기

• array와 linked list 비교

location	인접 위치에 저장	인접 위치에 저장 X
size	fixed	dynamic
momory	↓	↑
element access	쉬움	전체 linked list 탐색 필요
operation	시간이 걸림	빠르게 수행 가능

• direct access array 특징
  • 배열을 사용하여 record에 대응하는 key를 매핑한다. (비어있는 공간에 하나씩 할당)
  • 시간복잡성 : Ω(1)
• linked list를 사용할 경우 발생할 문제점
  : linked list는 임의적인 접근이 불가능하고 첫번째 요소부터 순차적으로 접근하기 때문에 Ω(n)이 소요됨을 알 수 있고 이는 Ω(1)로 접근가능한 direct access array보다 비효율적임을 알 수 있다. linked list 특성상 포인터를 위해 추가적인 메모리 공간이 필요할 수 있다.

3. birthday dataset 활용하기

• Birthday dataset에서 생일 날짜를 보여주는 열을 변수에 저장한 후 해당 열을 배열로 변환한다 -> 이때 결측값은 0으로 채우며 생일 날짜가 저장된 배열에 각각의 정렬 알고리즘을 적용해본다.
  • bd_val : Birthday dataset에서 생일 날짜를 보여주는 데이터프레임을 numpy 형태로 표현
    

    

  • bd_li : bd_val을 list 형태로 변환

3.1. unordered array set에 넣기

arr = bd_val
n = 5
print("unordered array set에 넣기\n")
print("insert 전: ")
for i in range(0,n) :
    print(arr[i],end='\n')
x = 12.31
pos = 3
unordered_arr(arr, n, x, pos)
n+=1
print("\ninsert 후: ")
for i in range(0,n) :
    print(arr[i],end='\n')

def unordered_arr(arr, n, insert_val, pos) :
    for i in range(n-1,pos-1,-1) :
        arr[i + 1] = arr[i]
    arr[pos] = insert_val

 

3.2. sorted array set에 넣기

size = len(bd_li)
n = 5
insert_val = 1.02
print("sorted array set에 넣기\n") 
print("insert 전: ", end="\n")
for i in range(n):
    print(bd_li[i], end="\n")
n = sorted_arr(bd_li, n, insert_val, size)
print("\ninsert 후: ", end="\n")
for i in range(n):
      print(bd_li[i], end="\n")

def sorted_arr(arr, n, insert_val, size):
    if (n >= size):
        return n
    i = n - 1
    while i >= 0 and arr[i] > insert_val:
        arr[i + 1] = arr[i]
        i -= 1
    arr[i + 1] = insert_val
    return (n + 1)

 

3.3. direct access array set에 넣기

arr = li
n = 5
print("direct access array에 넣기\n")
print("insert 전: ")
for i in range(0,n) :
    print(arr[i],end='\n')
x = 12.10
print("\ninsert 후: ")
daa(0,x)

table_size = 10
direct_table = [None] * table_size
def daa(key, insert_val):
        direct_table[key] = insert_val
        return direct_table

100개의 생일 데이터 존재, 따라서 size는 100

 

 

3.4. size 비교하기

• 100개의 생일 데이터 존재, 따라서 size는 100

3.5. interfaces 비교하기 : build, find, insert, delete, find_min, find_max, find_next, find_prev

buildfindinsertdeletefind_minfind_maxfind_nextfind_prev

unordered array	100	100	100	100	100	100	100	100
sorted array	100log100	log100	100	100	1	1	log100	log100
direct access array	u	1	1	1	u	u	u	u