참고자료

Grokking Algorithms
소프트웨어 속 알고리즘 #1 슬라이드
쥬피터 노트북 파일

극단적인 알고리즘의 성능차이

$O(n)$ : 선형시간 (n번연산)

def sum_n(n):
    s = 0
    for i in range(1, n + 1):
        s = s + i
    return s


print(sum_n(10))
print(sum_n(100))
55
5050

가우스 할아버지의 더하기 방법을 사용한 방법

$O(1)$ 상수시간 (1번연산: 크기에 상관없이 항상 똑같은 시간이 걸립니다.)

def sum_n(n):
    return n * (n + 1) // 2


print(sum_n(10))
print(sum_n(100))
55
5050

동일 결과의 더하기 연산이지만 두 번째 알고리즘은 $O(1)$의 복잡도를 가지게 됩니다.
알고리즘에 따라 결과가 극단적으로 바뀌는걸 보실 수 있습니다.

입력을 절반으로 나눈후 나눈 부분에 찾고자 하는 원소가 있는지 확인 하는 방법입니다.
(절반보다 크다, 작다 …..)
검색을 할때마다 절반의 제거되기 때문에 $O(\log{}n)$ 의 성능을 보이게 됩니다.

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None


my_list = [1, 3, 5, 7, 9, 4, 3213, 1221]

print(binary_search(my_list, 3))
print(binary_search(my_list, -1))
1
None

빅오 표기법 (Big O notation)

알고리즘의 성능은 대체로 빅오 표기법으로 표시합니다.
중요한점은 최악의 상황의 성능으로 표기한다는 점입니다.

표기법
$O(n)$ 
대문자 O로 표기
n은 연산횟수
  • $O(1)$ : 위의 가우스 할아버지 덧셈법, 크기에 상관없이 항상 똑같은 시간이 걸립니다.
  • $O(\log{}n)$ : 이진 탐색
  • $O(n)$ : 단순탐색
  • $O(n{}\log{}n)$ : 퀵정렬
  • $O(n^2)$ : 선택 정렬
  • $O(n!)$ : 외판원 문제

선택정렬 (selection sort)

모든 배열을 순환하는 방법으로 배열 아이템 하나에 대해 최소값을 찾는 반복문이 있어 $O(n^2)$ 의 성능을 보입니다.

def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index


def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr


print(selectionSort([5, 3, 6, 2, 10]))
[2, 3, 5, 6, 10]

재귀 (recursion)

함수가 자기 자신을 호출하는 식으로 동작합니다.
분할 정복(divide and conquer) 방법중 하나입니다.

보통의 사람들은 재귀를 아주 좋아하거나 아주 싫어한다.

case #1. 재귀를 사용하지 않는 경우의 의사코드(pseudo-code)

def look_for_key(main_box):
    pile = main_box.make_a_pile_to_look_through()
    while pile is not empty:
        box = pile.grab_a_box()
        for item in box:
            if item.is_a_box():
                pile.append(item)
            elif item.is_a_key():
                print("열쇠를 찾았어요!")

case #2. 재귀를 사용하는 경우의 의사코드(pseudo-code)

def look_for_key(box):
    for item in box:
        if item.is_a_box():
            look_for_key(item)
        elif item.is_a_key():
            print("열쇠를 찾았어요.")

“프로그램에 반복문을 사용하면 프로그램의 성능을 향상시킬 수 있지만, 재귀를 사용하면 프로그래머의 능력을 향상시킬 수 있습니다.” - 캐드웰 (Leigh Caldwell)

재귀를 사용한 코드가 더 명확해 보입니다. 그러나 성능상의 이점은 미미합니다.
꼬리 재귀(tail recursion)를 사용하면 반복문과 성능차이가 나지 않는다.

재귀를 이용한 카운트 다운
def countdown(i):
    print(i)
    # base case
    if i <= 0:
        return
    # recursive case
    else:
        countdown(i-1)

        
countdown(5)
5
4
3
2
1
0

스택 (stack)

호출 스택

함수 실행시마다 스택이 쌓인다.
함수 실행이 제거되면 쌓인 스택은 제거된다.

def greet(name):
    print("hello, " + name + "!")
    greet2(name)
    print("getting ready to say bye...")
    bye()
    
    
def greet2(name):
    print("how are you, " + name + "?")

    
def bye():
    print("ok bye!")
    
    
greet("maggie")
hello, maggie!
how are you, maggie?
getting ready to say bye...
ok bye!
재귀를 이용한 팩토리얼 구하기
def fact(x):
    if x == 1:
        return 1
    else:
        return x * fact(x-1)

    
print(fact(3))
6
재귀를 사용하지 않는 더하기
def sum(arr):
    total = 0
    for x in arr:
        total += x
    return total


print(sum([1, 2, 3, 4]))
10
재귀를 사용한 더하기
def sum(list):
    if list == []:
        return 0
    else:
        return list[0] + sum(list[1:])


print(sum([1, 2, 3, 4]))
10

퀵소트 (quicksort)

특정원소를 정하고 그 인덱스를 기준으로 정렬한다.
실행시마다 원소가 줄어들지만 상수항은 무시되지만 상수항은 무시되어 $O(n^2)$의 성능을 보인다.

def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)
    

print(quicksort([10, 5, 2, 3]))
[2, 3, 5, 10]
코드 설명

less 에 대한 경우는 입력된 리스트(array)의 루프를 돌며 pivot보다 작거나 같은 새로운 배열을 생성한다. (greater는 반대)

less = [i for i in array[1:] if i <= pivot]
array = [10, 5, 2, 3]
pivot = 2
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]

print(less)
print(greater)
[2]
[5, 3]

알고리즘 성능

case #1. 반복문을 사용한 기본적인 반복
def print_items(list):
    for item in list:
        print(item)
        

print_items([1, 3, 4, 5])
1
3
4
5
case #2. 1초간 정지하는 코드를 넣음 sleep(1)
from time import sleep
def print_items2(list):
    for item in list:
        sleep(1) #1초간 정지
        print(item)
        

print_items2([1, 3, 4, 5])
1
3
4
5

$c * n$ : c는 상수(constant), n은 실행횟수

1초의 상수시간이 있지만 상수를 곱한다고 해도 결과는 크게 변하지 않는다.