2.3 알고리즘의 설계(introduction to algorithms 3rd edition)

1. merge sort 직접 구현하기

def merge_sort(alist):
    div = int(len(alist)/2)
    if div > 0 :
        return merge(merge_sort(alist[:div]), merge_sort(alist[div:]))
    else :
        return alist

def merge(alist,blist):
    merged_list = []
    i=0
    j=0
    while(i<len(alist) and j<len(blist)):
        if alist[i] < blist[j]:
            merged_list.append(alist[i])
            i += 1
        else:
            merged_list.append(blist[j])
            j += 1
    if i == len(alist):
        merged_list.extend(blist[j:])
    else :
        merged_list.extend(alist[i:])
    return merged_list

python으로 merge sort를 구현했다.

첫단계에서 div 가 영보다 크면 리스트에 2개 이상의 원소가 있다는 것이므로 분할해서 merge sort를 콜한다.

결국 한개의 원소가 남을 때까지 내려가면 한개의 원소만 반환을 하고 merge에서 양쪽의 리스트를 합쳐주면 된다. 첫번째 인자로 받은 리스트의 원소가 크면 새로운 리스트에 먼저 넣고 그렇지 않으면 두 번째 리스트를 append해준다. 그리고 두 리스트중에 먼저 끝에 도달한 리스트를 확인하고 남은 값들을 merged_list에 붙여준다. 여기서 오류가 발생해서 시간을 꽤 지체 했는데 python에서 append는 오브잭트를 그대로 리스트에 붙여버리고, extend는 리스트 튜플 딕셔너리의 엘리먼트를 list에 붙여준다.

2. merge sort의 시간 복잡도는 O(nlg(n))이다 merge의 과정에서 cn만큼의 시간이 소요되고 재귀 트리의 레벨수는 lgn + 이기 때문이다. merge_sort가 호출될 때마다 리스트의 길이가 절반으로 줄어든다는 것을 생각해보면 된다.

연습문제

2.3-2

위에 파이썬으로 구현한 방식이다.

2.3-4

최악의 경우를 생각해보자 이미 분할의 과정에서 재귀적으로 n번 merge가 호출되도록 만들어져있으니 n. 그리고 각 merge의 경우시행 횟수가 1부터 n-1까지 증가하므로 전체 (n-1)n/2의 시간이 걸린다.

2.3-5

def binary_search(value,list):
    div = int(len(list)/2)
    if div>0 :
        if value == list[div]:
            print("yes")
            return
        elif value > list[div]:
            return binary_search(value,list[div:])
        else:
            return binary_search(value,list[:div])
    else:
        if value == list[0]:
            print("yes")
        else:
            print("no")

파이썬으로 구현한 binary_search 이미 정렬된 리스트이기 때문에 받은 리스트가 2개 이상이라면 value와 중간값을 비교해서 중간값보다 큰 리스트인지 작은 리스트인지 확인하고 value가 있을 것으로 예상되는 리스트와 함깨 재귀적으로 binary_search를 다시 호출해준다. 마지막으로 하나의 값을 가진 리스트를 받게되면 그 값이 value와 일치하는지 확인하고 일치하지 않을경우 존재하지 않는다고 알리고 끝낸다. 최악의 경우는 value가 리스트에 존재하지 않는 경우인데 인풋으로 받는 리스트의 값이 계속 절반으로 줄기 때문에 O(lg(n))의 값을 running time으로 갖는다.

2.3-6

insertion sort에서 시간복잡도는 선형검색에서 n, 서치하는 횟수 n으로 O(n^2)의 복잡도를 가진다. 그러나 선형검색을 lg(n)으로 바꿔주게된다면 수행시간을 O(nlgn)으로 개선하는 것이 가능하다.

2.3-7

집합 S를 merge sort로 정렬(nlgn) + x값보다 작거나 같은 값들을 찾기위해 이진검색(lgn) +  앞에서 구한 값에 몇을 더해햐 x가되는지 계산후 이진검색(lgn)*(작은 값들의 갯수 약 n) 따라서 nlgn의 시간복잡도를 갖는다.

2단원 정리

삽입 정렬 :  주어진 리스트에서 다음원소가 삽입 될 장소를 검색 후 올바른 위치에 삽입하여 루프 불변성을 유지한다

선택 정렬 : 가장 작은 원소를 찾고 맨 앞으로 옮기는 작업을 반복한다.

The divide-and-conquer approach : 문제를 일정한 규칙으로 쪼개서 가장 작은 단위로 만들고 다시 합쳐서 결과값을 찾아낸다. 재귀적으로 문제를 해결하기 편함.

병합 정렬 :  리스트를 둘로 쪼개기를 반복한다. 쪼개진리스트를 정렬하면서 다시 붙인다. O(nlgn)의 복잡도를 갖는다.

loop invariant : initialization, maintenance, termination의 단계를 거친다. 수학적 귀납법과 유사하나 종료시점도 체크를 해줘야 한다는 점이 다르다. 초기값이 올바른지 확인하고 값을 변화에따라 여전히 규칙이 불변하는지 확인하고, 마지막으로 종료시점까지 값의 규칙을 확인.

Bubble sort : 처음에는 리스트의 가장 오른쪽부터 왼쪽 끝까지 작은 원소를 만날 때마다 교체, 그러면 맨왼쪽 끝에는 가장 작은 원소가 위치한다. 다음에는 왼쪽에서 두번째까지 이런식으로 마지막까지 정렬해준다.

binary search : 정렬된 리스트를 기준으로 선형검색에 걸리는 복잡도 n을 lgn으로 줄여준다. 그러나 정렬되지 않은 경우에는 정렬에 시간이 걸린다. 정렬된 리스트를 반으로 나누어서 value가 속할 확률이 있는 리스트를 대상으로 재귀함수를 이용한다

python tip : append는 object를 그대로 붙이고, extend는 리스트, 튜플, 딕셔너리의 값들을 리스트의 뒤에 원소별로 붙여준다.