Problem Set 2

Assignment 2

• All your assignments should be uploaded on your blog. In LMS, leave your address. 
• You should use Korean.
• Due date: Next Tuesday 12:00 (noon!)
• No late submissions will be accepted except official excuses.

1. Solve the problems 34 in chapter 

1. The solution is provided. 
2. Try to solve the problem without the solution and compare. 
3. What is the difference between your original solution and solution provided?

2. Apply sorting algorithms to the birthday dataset.

1. Prove correctness of each algorithm
2. Argue efficiency of each algorithm

 

 

1. 34번 풀어보기

[문제]

아래 중첩된 루프의 시간 복잡도 T(n)은 얼마인가요? 간단하게, n은 2의 거듭제곱이라고 가정할 수 있습니다. 즉, 양의 정수 k에 대해 n = 2k입니다.

 

[풀이]

(1) 스스로 문제 풀이

i) 밖에 있는 while문은 n부터 시작해서 1까지, 매번 반으로 나누면서 진행한다. → log(n)

ii) 안에 있는 while문(4번째 줄)에서 j는 n을 초과하기 전까지 반복하고 6번째 줄에 따라 각 반복에서 2배가 되기 때문에 log2(n/i)번 반복됨 → log(n/i)

iii) 전체 시간 복잡도는 outer문과 inner문의 시간 복잡도의 곱이다. 

    → O(log n)*O(log(n/i))*O(1)=O(log^2 (n/i))

이 문제에서 i = n으로 설정되었기 때문에 worst 시간 복잡성은 O(log^2 n)이다.

 

(2) 답지와의 비교

 

 

 

1. Birthday dataset에  sorting 알고리즘 적용해보기

1) 순열 정렬

2) 선택 정렬

3) 병합 정렬  

 

[1] 순열 정렬

- permutation sort(순열 정렬): 모든 경우의 수를 다 살펴보는 정렬 알고리즘

Python implementation :
def permutation_sort(A):
for B in permutations(A):
if is_sorted(B):
return B

시간 복잡도: Ω(n!n) - 최악의 경우 permutations에서 n! x if 절에서 n 만큼 걸리기 때문.

- 정확성

  permutation sort는 요소가 하나 있을 때는 이미 정렬이 된 리스트이고, k크기의 리스트에 대해 모두 정렬된 리스트를 생성한다고 가정하면 for루프가 반복되면서 정렬을 확인하고 출력을 한다. 따라서 k+1 크기의 리스트에 대해서 정렬된 리스트의 순열이 만들어진다. → 정확한 결과가 나온다. 

- 효율성

 순열 정렬은 모든 경우의 수를 다 확인하기 때문에 효율성이 떨어진다.

 

 

[2] 선택 정렬

 

<강의 자료에서 알려준 코드>

def prefix_max(A, i):
'''Return index of maximum in A[:i + 1]'''
if i > 0:
j = prefix_max(A, i-1)
if A[i] < A[j]:
return j
return i


def selection_sort (A, i = None) :
'''Sort A[:i + 1]'''
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)

def selection_sort(birth):
	for i in range(len(birth) - 1):
    	min_index = i
        for j in range(i+1, len(birth)):
        	if birth[min_index] > birth[j]:
            	min_index = j           
        birth[min_index], birth[i] = birth[i], birth[min_index]

- 정확성

  리스트의 크기가 k일 때 이 알고리즘이 성립한다고 가정을 한다. 리스트의 길이가 k+1일 때 k길이의 리스트를 정렬할 수 있다.  따라서 k+1일 때도 이 알고리즘이 성립한다.

  → 정확한 결과가 나온다.

- 효율성

  선택정렬은 시간복잡도가 O(n^2)이다. outer문과 inner문이 모두 n번 반복하며 돌기 때문이다. 

 

[3] 병합 정렬

 

def merge_sort(birth):
    if len(birth) > 1:
        mid = len(birth) // 2
        left_half = birth[:mid]
        right_half = birth[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                birth[k] = left_half[i]
                i += 1
            else:
                birth[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            birth[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            birth[k] = right_half[j]
            j += 1
            k += 1

    return birth

 

- 정확성

  리스트의 길이가 하나 있을 때는 항상 정렬되어있다.

  리스트의 크기가 k일때, k+1일때 리스트를 정렬하는 경우 우선 반으로 나눠 각각 정렬하게 되고 리스트를 병합할때 문제    가 없기 때문에 알고리즘이 성립한다. → 정확한 결과가 나온다.

- 효율성

  O(nlogn)