좋은 알고리즘이란? / 알고리즘 평가법

 

좋은 알고리즘이란? / 알고리즘 평가법

 

 

좋은 코드 기준

 

• 시간
• 공간 (컴퓨터의 저장공간)

---

시간 복잡도 (Time Complexity)

 

데이터가 많아질수록 걸리는 시간이 얼마나 급격히 증가하는가

 

---

시간 복잡도를 계산하려면 알아야하는 약간의 수학 지식

 

• 거듭제곱과 로그
• 1부터 n까지의 합

---

점근 표기법(Big-O Notation)

 

n 의 영향력이 더 큰 곳을 찾으면 된다.

 

핵심 : n 이 엄청 크다고 가정

 

n 이 별로 크지 않으면, 안 좋은 알고리즘을 써도 문제 없다.

 

n 이 엄청 크다고 가정하므로 n 의 영향력이 큰쪽이 나중에 커질수밖에 없다.

절대적인 시간이 아닌 성장성이 가장 중요하다.

n제곱이 n 이나 상수 같은 값에 비해 훨씬 더 큰 값이므로 나머지 값은 큰 영향을 주지 않는다고 생각하여 O(n제곱)만 표기하게 된다.

---

점근 표기법의 의미

 

점근 표기법의 인풋 크기에 따른 의미

 

인풋이 커짐에 따라 비효율적임이 들어나는 O(n세제곱)

 

공간(컴퓨터의 사양)보다 더 중요한 건 시간(알고리즘)이라는 걸 보여주는 이미지

---

선형 탐색의 최선과 최악의 상황에서의 시간 복잡도 계산

이진 탐색의 최선과 최악의 상황에서의 시간 복잡도 계산

가장 영향력이 큰 n 을 남기고 나머지 상수같은건 모두 배제한다. (어차피 n 값이 매우 크다고 가정한다면 나머지 수는 영향이 거의 없기 때문에)

---

알고리즘 평가 주의 사항

 

 

점근 표기법에서 n 은 무엇인가?

 

점근 표기법에서 n 이 갖는 의미에 대해 착각하는 사람들이 많은데, 사실 n 은 점근 표기법에서 인풋 크기를 나타낼 때 가장 흔히 사용되는 문자일 뿐, 별다른 의미는 없다. 인풋 리스트의 크기는 x 라고 부르기로 하면 O(x), O(x제곱) 등의 표기를 할 것이다.

 

 

코드의 모든 줄은 O(1) 인가?

 

아니다. 인풋 크기와 상관 없이 실행되는 코드만 O(1)이다. 그렇지 않은 코드는 시간 복잡도를 따져봐야 하는데, 예를 들어 sorted 함수나 sort 메소드를 사용하면 내부적으로 O(n lg n)의 정렬이 이루어진다. 만약 리스트에서 in 키워드를 통해 값의 존재 여부를 확인하면 내부적으로 O(n)의 선형 탐색이 이루어질 것이다.

 

 

List Operations (리스트의 길이 = n 이라고 가정)

 

 

Dictionary Operations

 

---

주요 시간 복잡도 총정리 (예시)

 

 

알고리즘의 시간 복잡도는 대개 이 중 하나이다.

 

• O(1)
• O(lg n)
• O(n)
• O(n lg n)
• O(n제곱)
• O(n세제곱)
• O(n네제곱)
• O(2의 n제곱)
• O(n!)

이 중에서도 위에서부터 6개가 많이 사용되고 나머지도 흔치 않다.

O(1), O(lg n), O(n), O(n lg n), O(n제곱), O(n세제곱)

 

 

O(1)

 

 

O(1) 은 인풋의 크기가 소요 시간에 영향이 없다는 뜻이다.

 

def print_first(my_list):
    print(my_list[0])

print_first([2, 3])
print_first([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53])

print_first 함수를 처음 호출할 때나 두번째 호출할 때나 리스트의 크기에 상관없이 걸리는 시간은 거의 같다.

반복문이 없으면 대체로 O(1) 이라고 보면 된다.

 

 

O(n)

 

 

Case 1

def print_each(my_list):
    for i in range(len(my_list)):
        print(my_list[i])

반복문이 있고, 반복되는 횟수가 인풋의 크기와 비례하면 일반적으로 O(n) 이다.

 

Case 2

def print_half(my_list):
    for i in range(len(my_list) // 2):
        print(my_list[i])

n번 반복하는 게 아니라 n / 2 번 반복한다면 시간 복잡도는 어떻게 될까? O(1/2n) 이지만, 앞에 붙은 상수는 버려서 결론적으로 O(n)이라고 할 수 있다.

 

Case 3

def print_three_times(my_list):
    for i in range(len(my_list)):
        print(my_list[i])

    for i in range(len(my_list)):
        print(my_list[i])

    for i in range(len(my_list)):
        print(my_list[i])

위 코드의 경우 O(3n)인데, 결국에는 O(n)이라고 할 수 있다.

 

 

O(n제곱)

 

 

그런데 반복문이 연속해서 나오는게 아닌, 반복문 안에 반복문이 있는 경우가 있다.

def print_pairs(my_list):
    for i in range(len(my_list)):
        for j in range(len(my_list)):
            print(my_list[i], my_list[j])

지금처럼 두 반복문 다 인풋의 크기에 비례하는 경우, O(n제곱)이라고 할 수 있다.

 

 

O(n세제곱)

 

 

def print_triplets(my_list):
    for i in range(len(my_list)):
        for j in range(len(my_list)):
            for k in range(len(my_list)):
                print(my_list[i], my_list[j], my_list[k])

동일한 원리로, 인풋의 크기에 비례하는 반복문이 세 번 중첩되면 O(n세제곱)이 된다.

 

 

O(lg n)

 

 

Case 1

#2의 거듭제곱을 출력하는 함수
#이번에는 인풋이 리스트가 아니라 그냥 정수)
def print_powers_of_two(n):
    i = 1
    while i < n:
        print(i)
        i = i * 2

이번에는 반복문이 조금 특이한데, i 가 두 배씩 증가한다.

 

인풋 n 이 128이면 반복문이 총 몇 번 실행될까? i 가 1일 때부터 2, 4, 8, 16, 32, 64 까지 총 7번 실행된다. lg 128도 7인건 우연이 아니다.

 

print_powers_of_two 함수는 O(lg n) 이다.

 

 

Case 2

# 2의 거듭제곱을 출력하는 함수
# 이번에는 인풋이 리스트가 아니라 그냥 정수
def print_powers_of_two(n):
    i = n
    while i > 1:
        print(i)
        i = i / 2

n 부터 시작해서 반씩 나눈다. 이 경우에도 i 가 128 부터 64, 32, 16, 8, 4, 2 까지 반복문이 7번 실행된다.

 

두 경우 모두 O(lg n) 이다.

 

 

O(n lg n)

 

 

O(n) 과 O(lg n) 이 겹쳐진 것이다.

 

Case 1

def print_powers_of_two_repeatedly(n):
    for i in range(n): # 반복횟수: n에 비례
        j = 1
        while j < n: # 반복횟수: lg n에 비례
            print(i, j)
            j = j * 2

위 코드에서 for문의 반복횟수는 n에 비례하는데, while 문의 반복횟수는 lg n 에 비례한다. while 문이 for 문 안에 중첩되어 있기 때문에 위 코드의 시간 복잡도는 O(n lg n) 이라고 할 수 있다.

 

Case 2

def print_powers_of_two_repeatedly(n):
    i = 1
    while i < n: # 반복횟수: lg n에 비례
        for j in range(n): # 반복횟수: n에 비례
            print(i, j)
        i = i * 2

Case 1 의 코드를 살짝 바꿔서 이제 for 문이 while 문 안에 중첩되어 있다. 이 경우에도 시간 복잡도는 O(n lg n) 이다.

---

공간 복잡도

 

 

인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 나타낸다. 공간 복잡도도 Big-O 표기법을 사용할 수 있다.

 

 

O(1)

 

def product(a, b, c):
    result = a * b * c
    return result

파라미터 a, b, c 가 차지하는 공간을 제외하면 추가적으로 변수 result 가 공간을 차지한다. result 가 차지하는 메모리 공간은 인풋과 무관하기 때문에 함수 product 의 공간 복잡도는 O(1) 이다.

 

 

O(n)

 

def get_every_other(my_list):
    every_other = my_list[::2]  # 0번 인덱스부터 2 간격
    return every_other

인풋 my_list 의 길이를 n 이라고 하자.

 

파라미터 my_list 가 차지하는 공간을 제외하면 추가적으로 변수 every_other 이 공간을 차지한다. every_other 이 차지하는 공간은 어떻게 표현할 수 있을까?

 

리스트 every_other 에는 my_list 의 짝수 인덱스의 값들이 복사돼서 들어간다. 약 n/2 개의 값이 들어간다는 것이다. O(n/2) 는 O(n) 으로 나타내기 때문에, get_every_other 함수의 공간 복잡도는 O(n) 이다.

 

 

O(n제곱)

 

def largest_product(my_list):
    products = []
    for a in my_list:
        for b in my_list:
            products.append(a * b)
    
    return max(products)

인풋 my_list 의 길이를 n 이라고 하자.

 

파라미터 my_list 가 차지하는 공간을 제외하면 추가적으로 변수 products, a, b 가 공간을 차지한다. 우선 a와 b는 그냥 정수 값을 담기 때문에 O(1) 이다. 그렇다면 products 가 차지하는 공간은 어떻게 표현할 수 있을까?

 

리스트 products 에는 my_list 에서 가능한 모든 조합의 곱이 들어간다. 그렇다면 총 n제곱 개의 값이 들어갈 것이다. 따라서 largest_product 의 공간 복잡도는 O(n제곱)이다.

---

유용한 파이썬 기능 정리

 

 

type

 

print(type([7, 5, 2, 3, 6]))
print(type(5))
print(type(3.14))
print(type(True))
print(type("True"))

#<Run>
#<class 'list'>
#<class 'int'>
#<class 'float'>
#<class 'bool'>
#<class 'str'>

type 함수를 사용하면 파라미터의 데이터 타입이 리턴된다. 시간 복잡도는 O(1) 이다.

 

 

max, min

 

print(max(2, 5))
print(max(2, 7, 5))
print(min(2, 5))
print(min(2, 7, 5, 11, 6))

#<Run>
#5
#7
#2
#2

max 함수를 사용하면 파라미터 중 가장 큰 값이 리턴되고, min 함수를 사용하면 파라미터 중 가장 작은 값이 리턴된다. 두 함수 모두 파라미터 개수가 유동적이기 때문에 원하는 만큼 넘겨 줄 수 있다.

 

파라미터의 개수를 n 이라고 하면, max 함수와 min 함수의 시간 복잡도는 O(n) 이다.

 

 

str

 

my_str = str(257138)
print(my_str)
print(type(my_str))

#<Run>
#257138
#<class 'str'>

str 함수를 사용하면 숫자를 문자열로 바꿀 수 있다.

 

파라미터를 n이라고 하고 n 의 자릿수를 d 라고 하자. 그러면 str 함수의 시간 복잡도는 O(log n) 으로 나타낼 수도 있고 O(d) 로 나타낼 수도 있다.

 

 

append, insert, del, index, reverse

 

my_list = [7, 5, 2, 3, 6]

my_list.append(9)            # 끝에 9 추가
print(my_list)

my_list.insert(2, 11)        # 2번 인덱스에 11 추가
print(my_list)

del my_list[2]               # 2번 인덱스 값 삭제
print(my_list)

my_index = my_list.index(9)  # 리스트에서 9의 인덱스
print(my_index)

my_list.reverse()            # 리스트 뒤집기
print(my_list)

#<Run>
#[7, 5, 2, 3, 6, 9]
#[7, 5, 11, 2, 3, 6, 9]
#[7, 5, 2, 3, 6, 9]
#5
#[9, 6, 3, 2, 5, 7]

append 메소드를 사용하면 리스트 끝에 새로운 값이 추가된다. 시간 복잡도는 O(1) 이다.

insert, del, index, reverse 는 모두 O(n) 이다.

 

 

sort, sorted

 

my_list = [7, 5, 2, 3, 6]

print(sorted(my_list))
print(my_list)

my_list.sort()
print(my_list)

#<Run>
#[2, 3, 5, 6, 7]
#[7, 5, 2, 3, 6]
#[2, 3, 5, 6, 7]

sort 메소드와 sorted 함수는 리스트를 정렬시켜 줍니다. sorted 함수를 사용하면 정렬된 새로운 리스트가 리턴되고, sort 메소드는 그 리스트 자체를 정렬시켜 준다는 차이점이 있다.

 

두 메소드의 시간 복잡도는 모두 O(n lg n) 이다.

 

 

slicing

 

my_list = [7, 5, 2, 3, 6]

print(my_list[1:4])          # => [5, 2, 3]
print(my_list[:4])           # => [7, 5, 2, 3]
print(my_list[1:])           # => [5, 2, 3, 6]
print(my_list[:])            # => [7, 5, 2, 3, 6]
print(my_list[::2])          # => [7, 2, 6]

#<Run>
#[5, 2, 3]
#[7, 5, 2, 3]
#[5, 2, 3, 6]
#[7, 5, 2, 3, 6]
#[7, 2, 6]

리스트 슬라이싱을 하면 리스트의 일부를 받아 올 수 있다. 리스트 슬라이싱의 시간 복잡도는 슬라이싱의 범위 길이에 비례한다. my_list[a:b] 를 하면 시간 복잡도는 O(b-a) 이다.

 

 

len

 

my_list = [7, 5, 2, 3, 6]
my_dict = {'a': 2, 'b': 3, 'c': 5, 'd': 7}
my_string = 'hello world'

print(len(my_list))
print(len(my_dict))
print(len(my_string))

#<Run>
#5
#4
#11

len 함수를 사용하면 리스트, 사전, 문자열 등의 길이가 리턴된다. 시간 복잡도는 O(1) 이다.