알고리즘 수업 과제 2

1. 34번 문제를 풀어보고 본인의 풀이와 해답과의 차이를 설명하라.
   34번 문제는 다음과 같습니다.

What is the time complexity T(n) of the nested loops below? For simplicity, you
may assume that n is a power of 2. That is, n = 2k for some positive integer k.

i = n ;
while ( i >= 1) {
j = i ;
	while ( j <= n) {
		< body o f the while loop> //Needs ( 1 ) .
		j = 2 * j;
		}
	i = floor(i /2) ;
}

이 알고리즘의 시간 복잡도는 O(log2n^2)라 생각했다.
우선 수업 시간에 배운대로 outer loop와 inner loop가 존재하므로 이 둘을 곱해야 하는데, outer loop는 i가 1이 될 때까지 2로 나눠지므로 log2n 이되고 inner loop는 j가 n이 될 때까지 제곱이 되므로 똑같이 log2n 이 되기 때문에 총 시간 복잡도는 log2n^2 가 된다고 생각했다.
해답과 답은 동일했지만, 풀이 식이 달랐다. 답 풀이: T(n) = (log2n + log n)/2 = O(log2n) 인데, 일단 큰 형태로는 두 시간복잡도를 더하는 부분에서 차이가 있다. 또한 이 더한 식을 2로 나누는데, 이 풀이가 이해가 안돼서 여쭤볼 예정이다.

2. birthday dataset에 정렬 알고리즘을 적용시켜라.

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

#birthday dataset list로 읽어오기. 모든 정렬코드에서 이 리스트를 사용
import pandas as pd
df = pd.read_csv('/Users/hansunkyoung/Projects/algorithm/BirthdayData.csv', encoding='UTF-8')
birth_df = df.iloc[1:, 2:3]


def permutation_sort(birth_df):
	for i in permutations(birth_df):
    	if is_sorted(i):
        	return i

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

정확성 증명:
1. 요소가 하나 있을 때는 이미 정렬이 된 리스트이다. - 참
2. k 크기의 리스트에 대해 모두 정렬된 리스트를 생성한다고 가정, for 루프가 반복되면서 정렬을 확인하고 출력을 하기 때문에 k+1 크기의 리스트에 대해서 정렬된 리스트의 순열이 만들어진다. - 참
1, 2 모두 올바르므로(참이므로) 결과는 정확하다고 볼 수 있다.

b. selection sort (선택 정렬) : 정렬이 안된 배열에서 최솟값을 탐색하고 맨 앞의 요소와 바꾼다.
(사실 수업시간에는 큰 요소를 찾고 이를 맨뒤로 보낸다고 배웠지만, 이게 더 알고리즘 구성이 복잡해서 이 알고리즘을 선택했다.)

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

시간 복잡도: O(n^2) - outer loop와 inner loop 모두 n번 반복하며 돌기 때문.

정확성 증명:
1. 요소가 하나 있을 때는 이미 정렬이 된 리스트이다. - 참
2. k 크기의 리스트가 정렬이 되었다고 가정, k+1 크기의 리스트를 정렬하는 경우 루프의 첫번째에서 제일 작은 요소가 스왑되면서 정렬되지 않은 부분의 크기가 k가 된다. 이는 가설로 부터 참이 유도된다.
1, 2 모두 올바르므로(참이므로) 결과는 정확하다고 볼 수 있다.

c. merge sort (병합 정렬): 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분리스트를 정렬한 다음, 두 리스트를 합하여 전체가 정렬된 리스트를 만드는 알고리즘.

def merge_sort(birth_df):
    if len(birth_df) > 1:
        mid = len(birth_df) // 2
        left_half = birth_df[:mid]
        right_half = birth_df[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_df[k] = left_half[i]
                i += 1
            else:
                birth_df[k] = right_half[j]
                j += 1
            k += 1

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

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

    return birth_df

시간복잡도: O(nlogn) - 리스트를 분할 하면 반복 횟수가 절반씩 줄어드므로 logn 이 되고, 각 반복에서 병합 시 값 비교를 해야하므로 x n 이 되기 때문.

정확성 증명:
1. 요소가 하나 있을 때는 이미 정렬이 된 리스트이다. - 참
2. k 크기의 리스트는 모든 하위 목록을 올바르게 분할, 병합하여 정렬한다고 가정, k+1 크기의 리스트를 정렬하는 경우 우선 반으로 나눠 각각을 정렬하게 되고 분할된 하위목록이 생성된다. 그리고 정렬된 하위목록들을 병합하여 리스트를 생성한다. 이는 가설로 부터 참이 유도된다.
1, 2 모두 올바르므로(참이므로) 결과는 정확하다고 볼 수 있다.

이 세개의 정렬 알고리즘 중에서는 병합 정렬이 시간 복잡도가 제일 작아 효율적인 것으로 보인다.