MIT 6.00 9회차 강의후기

License

License: Creative Commons BY-NC-SA

9회차

[MIT OpenCourseWare 6.00 9회차]

이진 탐색

정렬된 리스트가 있다고 생각하고 리스트의 범위를 잡은 뒤 midpoint를 구해 절반씩 버려가며 이진 탐색을 시행한다.
이후 마지막으로 남은 2개를 검사한다.

이진탐색은 강력하지만 반드시 선형탐색보다 빠른 것은 아니다.

Binary

def bsearch(s,e,first,last,calls):
    print(first, last, calls)
    if (last - first) < 2:
            return s[first] ==e or s[last] == e
    mid = first + int((last - first)/2)
    if s[mid] == e:
            return True
    if s[mid] > e :
            return bsearch(s,e,first,mid-1, calls+1)
    return bsearch(s,e,mid+1, last, calls+1)

def search(s,e):
    print(bsearch(s,e,0, len(s)-1, 1))

s = range(10000000)

search(s,-1)

result

0 9999999 1
0 4999998 2
0 2499998 3
0 1249998 4
0 624998 5 
0 312498 6
0 156248 7
0 78123 8
0 39060 9
0 19529 10
0 9763 11
0 4880 12
0 2439 13
0 1218 14
0 608 15
0 303 16
0 150 17
0 74 18
0 36 19
0 17 20
0 7 21
0 2 22
0 0 23
False

Linear

def search(s,e):
    answer = None
    i = 0
    numCompares = 0
    while i < len(s) and answer == None:
            numCompares += 1
            if e == s[i]:
                    answer = True
            elif e < s[i]:
                    answer = False
            i +=1
    print(answer, numCompares)

s = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

search(s,-1)

result

False 1

이진탐색을 시행할 때 -1을 찾으면 절반씩 버려가며 -1인지를 찾지만,
선형탐색에서는 곧바로 아닌 것을 찾아낸다.

LISP 같은 프로그램에서는 리스트 안을 차지하는 각각의 자료형의 메모리가 다를 수 있다.
이 경우 O는 선형이다.

파이썬의 경우 리스트를 포인터들의 리스트로 구성을 하여 빠른 검색이 가능하다.

로그 알고리즘

1. 중간 지점을 뽑는다.
2. 이것이 내가 찾던 값인지 확인한다.
3. 만약 아니라면 더 작은 문제로 줄이고 반복해라.

이러한 알고리즘은 Divide & Conquer 를 잘 표현해준다.
(큰 문제를 풀기 위해 작은 문제로 쪼갠 뒤 해결한다)

검색 전에 정렬을 해야할까?

1회 검색의 경우

정렬을 하는데 big-O는 n logn이다.
따라서 정렬을 하고 검색한다면 n logn + logn의 big-O가 될 것이다.
일반적으로 선형탐색에 걸리는 시간인 n은 nlogn + logn보다 작다.
(정렬하지 않는 것이 더 빠르다)

k회 검색의 경우

선형, 비정렬의 경우 k회 시도한 검색의 big-O는 kn이다.
이때 정렬 검색의 big-O는 nlogn + klogn으로 kn보다 작다.
(정렬하는 것이 더 빠르다)

선택정렬

인덱스의 맨 처음부터 마지막까지 반복해서,
i+1부터 인덱스의 마지막까지 비교해서 최솟값을 저장해 두었다가
로테이션이 끝날 때 i+1과 최솟값를 교환해주는 알고리즘

def selSort(L):
        for i in range(len(L) - 1):
                print (L)
                minIndx = i
                minVal= L[i]
                j = i + 1
                while j < len(L):
                        if minVal > L[j]:
                                minIndx = j
                                minVal= L[j]
                        j = j + 1
                temp = L[i]
                L[i] = L[minIndx]
                L[minIndx] = temp

def testSelSort():
        test1 = [1,6,3,4,5,2]
        input('run selective test 1')
        selSort(test1)
        test2 = [6,1,2,3,4,5]
        input('run selective test 2')
        selSort(test2)
        test3 = [6,5,4,3,2,1]
        input('run selective test 3')
        selSort(test3)
        test4 = [1,2,3,4,5,6]
        input('run selective test 4')
        selSort(test4)

testSelSort()

result

run selective test 1
[1, 6, 3, 4, 5, 2]
[1, 6, 3, 4, 5, 2]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
run selective test 2
[6, 1, 2, 3, 4, 5]
[1, 6, 2, 3, 4, 5]
[1, 2, 6, 3, 4, 5]
[1, 2, 3, 6, 4, 5]
[1, 2, 3, 4, 6, 5]
[6, 5, 4, 3, 2, 1]
[1, 5, 4, 3, 2, 6]
[1, 2, 4, 3, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
run selective test 4
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]

리스트의 길이를 10이라고 가정 해보았을때 선택정렬의 최악의 경우는 10 + 9 + 8 + ... 1
= 10(10+1)/2 = 55
= n(n+1)/2
= O(n*n)
= O(n^2)

선택정렬은 루프 불변성을 이용한다.

루프 불변성

루프를 통과할때 마다 항상 참이 되는 특성
루프가 실행중에 항상 만족해야하는 조건

 

- 초기 조건 : 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 유지되어야 한다.

 

- 유지 조건 : 루프가 반복되기 전에 루프 불변성이 유지되었다면 다음 반복이 시작되기 전까지도 계속 유지되어야 한다.

 

- 종료 조건 : 루프가 종료될 때 유지된 루프 불변성이 알고리즘 타당성 증명에 의미가 있어야 한다.

 

[루프 불변성]

 

버블 정렬

리스트의 첫번째부터 시작해서, 매번 그 다음 리스트의 요소와 비교해 정렬하는 것.  
원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.  
비효율적이기 때문에 자주 쓰이지 않는다.

 

def bubbleSort(L):
    for j in range(len(L)):
        print (L)
        for i in range(len(L) - 1):
            if L[i] > L[i+1]:
                temp = L[i]

                L[i] = L[i+1]
                L[i+1] = temp

def testBubbleSort():
    test1 = [1,6,3,4,5,2]
    input('run bubble test 1')
    bubbleSort(test1)
    test2 = [6,1,2,3,4,5]
    input('run bubble test 2')
    bubbleSort(test2)
    test3 = [6,5,4,3,2,1]
    input('run bubble test 3')
    bubbleSort(test3)
    test4 = [1,2,3,4,5,6]
    input('run bubble test 4')
    bubbleSort(test4)

testBubbleSort()

result

run bubble test 1
[1, 6, 3, 4, 5, 2]
[1, 3, 4, 5, 2, 6]
[1, 3, 4, 2, 5, 6]
[1, 3, 2, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
run bubble test 2
[6, 1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
run bubble test 3
[6, 5, 4, 3, 2, 1]
[5, 4, 3, 2, 1, 6]
[4, 3, 2, 1, 5, 6]
[3, 2, 1, 4, 5, 6]
[2, 1, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
run bubble test 4
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]

버블정렬의 big-O 또한 O(n^2)이다.

선택 정렬은 한번의 실행이 끝났을 때 한번 교환을 하고, 

버블 정렬은 더 큰 숫자를 만날때마다 매번 교환을 하기 때문에 선택 정렬이 더 효율적인 알고리즘이다.