MIT - Introduction to Computer Science and Programming in Python

이진 탐색

우리가 세운 이진 탐색의 기본적인 전제, 정렬된 원소들의 리스트를 가지고 있다고 상상해보는 것.
그리고 그 리스트에 있는 특정한 원소를 알고 싶다.
이진 탐색의 기본적인 아이디어는 우선 리스트의 전 범위에서 시작한다. 중점을 잡고 그 지점을 기준으로 테스트한다.
만약 그곳에 내가 찾던 것이 있으면 성공, 없으면 이 리스트는 정렬되어 있기 때문에 내가 찾고자 하는 것과 중간지점 사이의 차이를 이용해 찾을 수 있다.

e.g.1) binary search code

>>> 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, calls +1)
...
>>> def search(s,e):
...     print(bsearch(s,e,0, len(s)-1, 1))
...
>>> s = range(10000000)
>>> search(s,-1)
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

남아있는 곳에 닿을 때까지 한쪽에서 버려지고 또 다른쪽에서 버려지면서 범위를 좁히는 것을 볼 수 있다. 그러고 나서 찾는 숫자가 그곳에 있는지 없는지 말하기 위해서 2개를 검사한다.

복잡도,성장차수 : 로그 알고리즘

리스트를 반으로 나누는 것을 반복하여 원하는 값을 찾음

이 알고리즘이 실제로 무엇을 하는지?

로그 알고리즘

1. 중간지점을 뽑아라
2. 이것이 내가 찾고자했던것이니지 확인해라
3. 만약 아니라면, 더 작은 문제로 사이즈를 줄이고 반복해라

선형 탐색과 비교해서 생각해보자

선형탐색은 리스트의 처음에서부터 시작해서 한개씩 쭉 검사한다. 만약 운이 좋거나 리스트가 길지 않다면, 빨리 찾을 수 있을 것이다. 하지만 리스트가 굉장히 길다면, 오랜 시간이 걸릴 것이다.

정렬되지 않은 채 원소들이 들어있는 리스트가 있으면 무엇을 해야 할까?

탐색하기 전에 정렬을 해야한다면 얼마나 빠르게 정렬시킬 수 있나

답 : nlogn 시간에 할 수 있다.

선형시간안에 가능할까?
  - 선형시간안에서 리스트를 정렬시키기 위해서 기깟해야 일정한 시간내에 모든 원소를 비교해야한다.
    리스트가 얼마나 긴가에 따라 다르다.
    답은 그렇지 않다.

어떤 탐색 타입이 더 나은가?

2개의 변수가 있다.

1. 리스트의 길이
2. 탐색 횟수

한 번만 탐색하기 위해선 정렬 되지 않은 선형 탐색이 더 좋다. 왜냐하면 일반적으로 nlogn은 n,보다 크기 때문이다.

하지만 여러번 한다면?
리스트의 k search를 하고 싶다고 가정해본다면 다음 표와 같다.

이렇게 되면 일반적으로 nlogn + klogn은 kn보다 작아질 것이다.

선택 정렬

e.g.2) selection sort

>>> def selSort(L):
...     for i in range(len(L) -1):
...             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
...             print(L)
...
>>> 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()
run selective test 1
[1, 6, 3, 4, 5, 2]
[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 selective test 2
[1, 6, 2, 3, 4, 5]
[1, 2, 6, 3, 4, 5]
[1, 2, 3, 6, 4, 5]
[1, 2, 3, 4, 6, 5]
[1, 2, 3, 4, 5, 6]
run selective test 3
[1, 5, 4, 3, 2, 6]
[1, 2, 4, 3, 5, 6]
[1, 2, 3, 4, 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]
>>>

루프 불변성

루프를 통과할 때마다 항상 참의 되는 특성
리스트는 처음 요소와 마지막 요소로 나누어지고, 처음요소는 정렬되어지고 마지막 요소는 정렬되지 않는다.
이 루프는 기본적으로 마지막 요소에서 부터 시작되고 리스트의 끝에 닿을 때까지 1씩 증가한다.

복잡도,성장차수 : 이차

리스트 길이는 적어도 선형일 것이다.

버블 정렬

원소가 거품처럼 일어나기 때문에 버블정렬이라고 한다.
e.g.3) bubble sort

>>> def bubbleSort(L):
...     for j in range(len(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
...             print(L)
...
>>> 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()
run bubble test 1
[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]
[1, 2, 3, 4, 5, 6]
run bubble test 2
[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]
run bubble test 3'
[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]
[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]

복잡도, 성장차수 - 이차(n^2)

리스트의 요소의 교환을 이미 끝낸 것인지 아닌지 각각 살펴보는 건 어떨까
e.g.4) 불필요한 요소 교환 생략

>>> def bubbleSort(L):
...     swapped = True
...     while swapped :
...             swapped = False
...             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
...                             swapped = True
...             print(L)
...
>>> testBubbleSort()
run bubble test 1
[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
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
run bubble test 3
[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]
[1, 2, 3, 4, 5, 6]
run bubble test 4
[1, 2, 3, 4, 5, 6]

복잡도,성장차수 - 이차

이 알고리즘 들 중에서 뭐가 나은가? (선택 정렬 or 버블 정렬)

한 학생의 답 : 버블 정렬  
버블 정렬은 필요가 없으면 멈출 수 있기 때문에 선택 정렬보다 효율적이다.  

Q. 버블 정렬에서 몇 번 교환하는가?
A. 잠재적으로 아주 많다. 왜냐하면 계속 할 것이기 때문이다. 안쪽 루프에서 매우 많이 돌 것이다.

Q. 선택 정렬에서는 몇 번 교환하게 될까요?
A. 잠재적으로 단지 한번 교환을 한다. 잠재적으로 한 번은 아닐지라도, 루프의 끝에서 매번 교환하게 될 것이다.

이것은 사실 수행시간에 대한 성장차수가 같다는 것을 말한다. 아마 선택 정렬이 더 효과적인 알고리즘일 것이다. 일정한 양만큼 계속해서 하지는 않기 때문이다. 실제로 버블정렬을 한 경우는 보기 드물 것이다.