책 읽다가 코딩하다 죽을래
[알고리즘] 시간복잡도, 공간복잡도, 점근표기식 본문
1. 시간복잡도
시간 복잡도는 입력값에 따라 문제를 해결하는데 걸리는 시간과의 상관관계를 말합니다.
똑같은 알고리즘에 입력값이 몇 배로 늘어남에 따라 문제를 해결하는 데 걸리는 시간은 몇 배만큼 늘어나는지 보는 것이다.
우리는 똑같은 입력값이라도 당연히 더 빠른 시간 안에 입력을 처리하는 알고리즘을 선호한다.
즉 걸리는 시간이 줄어들수록 시간 복잡도는 작아지며, 시간 복잡도가 작은 알고리즘이 좋은 알고리즘이다.
시간 복잡도에 대해서 설명하기 위해
똑같은 목적을 가진 두 개의 알고리즘을 살펴보겠다.
두 개의 알고리즘의 목표는 배열 안에 숫자 중 가장 큰 최댓값을 찾는 로직이다.
array = [1,3,6,5,4,2]
def findMaxValue(array):
max_num = array[0]
for num in array: # array 의 길이만큼 아래 연산이 실행
for compare_num in array: # array 의 길이만큼 아래 연산이 실행
if num < compare_num: # 비교 연산 1번 실행
break
else:
return max_num
findMaxValue(array)
위의 알고리즘은 입력값인 배열 안에서 가장 큰 수를 정확히 찾아낸다.
그렇다면 얼마나 빨리 찾아내는지 계산하려면 어떻게 알아낼까?
답은 간단하다. 로직의 연산 수를 세 보면 된다.
저 로직의 반복문(for)이 두 번 들어가는데 각각 입력값인 array의 길이만큼 실행한다.
또 이 반복문은 따로 동작하는 것이 아니라
반복문 안에 반복문이 들어가서 두 개의 반복문이 종속적으로 실행된다.
즉 N x N이다.
여기서 N이란 입력값의 크기를 말하는데
우리가 길이가 10인 배열을 넣으면 N은 10이 되고
길이가 10000인 배열을 넣으면 N은 10000이 된다.
그런데 우리는 모든 경우의 수를 생각해야 하니 입력값의 길이를 N이라는 변수를 설정하는 것이다.
그다음 if 또는 else로 들어가는데 여기서 비교 연산이 1번 들어간다.
그러면 결과적으로 N x N + 1 = N^2 + 1 만큼 걸리는 것인데
상수는 앞에 N^2보다는 작으니 무시하므로
N^2만큼 걸린다고 말한다.
알고리즘 시간 복잡도를 구할 때 뒤에 상수값은 작은 값이니 무시한다.
뒤에서 배우겠지만 O(1)이 아닌 이상 상수값은 점근 표기법에 들어가지도 않는다.
다음 최댓값 찾기 알고리즘을 살펴보자
array = [1,3,6,5,4,2]
def findMaxValue(array):
max_num = array[0]
for num in array: # array의 길이만큼 아래 연산이 실행
if num > max_num: # 비교 연산 1번 실행
max_num = num # 대입 연산 1번 실행
return max_num
findMaxValue(array)
이 알고리즘의 시간 복잡도는
array 길이만큼 반복문이 실행되며
그 반복문 안에는 2개의 연산이 들어가 있다
즉 N *(1 + 1) + 1 = 2N + 1이며
상수는 버리므로
결과적으로 2N만큼의 시간 복잡도를 가지고 있다.
또한 시간 복잡도를 계산할 때 상수뿐만이 아니라
N의 계수도 버려야 한다.
즉 N의 지수만 갖고 가는 것이다.
그러므로 2N이 아니라 N이 된다
이 알고리즘도 위의 알고리즘처럼 똑같이 동작하는데 걸리는 시간은 다르다.
그리고 시간 복잡도는 작을수록 좋으니 당연히 N만큼의 시간 복잡도를 가진
후자의 알고리즘이 좋다고 볼 수 있다.
그러면 시간 복잡도가 얼마나 차이 나는지 직접 입력값의 개수를 늘려서 확인해보자
| N | N^2 + 1 | 2N + 1 |
| 1 | 2 | 3 |
| 10 | 101 | 21 |
| 100 | 10001 | 201 |
| 1000 | 1000001 | 2001 |
| 10000 | 100000001 | 200001 |
입력값이 커질수록 두 알고리즘의 시간 차이는 더욱 심해진다
똑같은 동작을 하는데도 알고리즘에 따라
1분이 걸릴 수도 1시간이 걸릴수도 있는 것이다.
알고리즘 시간 복잡도를 확인할 때
2가지를 보면 된다.
1. 상수는 버리고
2. N의 지수를 비교하면 된다.
그리고 입력값에 비례해서 얼마나 시간이 증가하는지를 보면 된다.
2. 공간복잡도
시간 복잡도와 달리 공간 복잡도는 입력값에 따라 문제를 해결하는 데 걸리는 공간과의 상관관계이다.
여기서 공간은 보통 메모리를 말하며
알고리즘이 실행하는데 쓰이게 되는 메모리 크기라고 생각하면 된다.
시간 복잡도와 마찬가지로 공간 복잡도도 작으면 작을수록 좋은 알고리즘이다.
당연히 메모리를 작게 사용할수록 시스템 성능도 좋기 때문이다.
이번에도 두 개의 알고리즘을 비교해서 설명해보겠다.
두 개의 알고리즘은 모두 문자열을 입력받아 문자열 중 많이 쓰인 알파벳을 찾는 로직이다.
def find_max_occurred_alphabet(string):
alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n",
"o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
# 26개의 공간을 사용
max_occurrence = 0 # 1개의 공간을 사용
max_alphabet = alphabet_array[0] # 1개의 공간을 사용
for alphabet in alphabet_array:
occurrence = 0 # 1개의 공간을 사용
for char in string:
if char == alphabet:
occurrence += 1
if occurrence > max_occurrence:
max_alphabet = alphabet
max_occurrence = occurrence
return max_alphabet
print(find_max_occurred_alphabet("bbaaaccd"))
# 결괏값 : a
공간 복잡도는 저장하는 데이터의 양이 1개의 공간을 사용한다고 계산하면 된다.
위의 알고리즘은 총
alphabet_array의 길이 = 26
max_occurrence, max_alphabet, occurrence 변수 = 3
29개의 공간 복잡도를 가진다
def find_max_occurred_alphabet(string):
alphabet_occurrence_list = [0] * 26 # 26개의 공간을 사용
for char in string:
if char.isalpha():
arr_index = ord(char) - ord('a') # 1개의 공간을 사용
alphabet_occurrence_list[arr_index] += 1
max_occurrence = 0 # 1개의 공간을 사용
max_alphabet_index = 0 # 1개의 공간을 사용
for index in range(len(alphabet_occurrence_list)):
alphabet_occurrence = alphabet_occurrence_list[index] # 1개의 공간을 사용
if alphabet_occurrence > max_occurrence:
max_occurrence = alphabet_occurrence
max_alphabet_index = index
return chr(max_alphabet_index + ord('a'))
print(find_max_occurred_alphabet("bbaaaccd"))
# 결괏값 : a
변수 하나의 크기를 1로 잡으면
alphabet_array 의 길이 = 26
arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
총 30개가 쓰인다
즉 30의 공간 복잡도를 가지고 있다 라고 생각하면 된다.
그러면 30보다는 29개의 공간복잡도를 갖는 전자의 알고리즘이 더 좋은 것인가?
물론 공간 복잡도만 놓고 본다면 맞는 말이지만 우리는 나무를 보지 말고 숲을 봐야 한다.
이 두 개의 알고리즘의 시간 복잡도를 계산해보자
우선 첫 번째 알고리즘의 시간 복잡도는
def find_max_occurred_alphabet(string):
alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n",
"o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
max_occurrence = 0
max_alphabet = alphabet_array[0]
for alphabet in alphabet_array: # alphabet_array의 길이(26) 만큼 아래 연산이 실행
occurrence = 0 # 대입 연산 1번 실행
for char in string: # string(N)의 길이만큼 아래 연산이 실행
if char == alphabet: # 비교 연산 1번 실행
occurrence += 1
if occurrence > max_occurrence: # 비교 연산 1번 실행
max_alphabet = alphabet # 대입 연산 1번 실행
max_occurrence = occurrence # 비교 연산 1번 실행
return max_alphabet26 * (1 + 2 * N + 3) = 52N + 104
즉 N이다.
두 번째 알고리즘의 시간복잡도는
def find_max_occurred_alphabet(string):
alphabet_occurrence_list = [0] * 26
for char in string: # string의 길이만큼 아래 연산이 실행
if char.isalpha(): # 비교 연산 1번 실행
arr_index = ord(char) - ord('a') # 대입 연산 1번 실행
alphabet_occurrence_list[arr_index] += 1 # 대입 연산 1번 실행
max_occurrence = 0 # 대입 연산 1번 실행
max_alphabet_index = 0 # 대입 연산 1번 실행
for index in range(len(alphabet_occurrence_list)): # alphabet_array의 길이(26)만큼 아래 연산이 실행
alphabet_occurrence = alphabet_occurrence_list[index] # 대입 연산 1번 실행
if alphabet_occurrence > max_occurrence: # 비교 연산 1번 실행
max_occurrence = alphabet_occurrence # 대입 연산 1번 실행
max_alphabet_index = index # 대입 연산 1번 실행
return chr(max_alphabet_index + ord('a'))
print(find_max_occurred_alphabet("bbaaaccd"))
N * (1 + 2) + 2 + 26 * (1 + 3) = 3N + 106
즉 N이다.
둘 다 똑같은 N이긴 하지만
이번엔 자세히 비교해보자
| N | 52N + 104 | 3N + 106 | N^2 |
| 1 | 156 | 109 | 1 |
| 10 | 624 | 136 | 100 |
| 100 | 5304 | 406 | 10000 |
| 1000 | 52104 | 3106 | 1000000 |
| 10000 | 520104 | 30106 | 100000000 |
이 표를 보면 데이터 수가 많아질수록
29의 공간 복잡도와 52N + 104 시간 복잡도를 가진 첫번째 알고리즘보단
30의 공간복잡도와 3N + 106 시간 복잡도를 가진 두번째 알고리즘이 더 낫다는 걸 알 수 있다.
그냥 1개의 메모리를 소비해서 더 많은 시간을 아끼는 것이 효율적이기 때문이다.
또한 52N이든 3N이든 N^2에 비하면 정말 아무것도 아니란 것을 알 수 있다.
정리해서 말하자면
시간복잡도를 계산할 때 N의 계수보단 지수를 신경 써야 한다.
공간 복잡도보다는 시간 복잡도가 더 중요하다
왜냐하면 사용자는 게임이나 어떤 웹사이트를 사용할 때
그 게임이 얼마나 많은 메모리를 잡아먹는지 보다는
렉이 걸리지 않는지 로딩 시간이 길지 않는지를 더 신경 쓰기 때문이다.
그렇다고 절대적으로 공간 복잡도는 중요하지 않고 배울 필요가 없다는 것은 아니다.
단지 우리는 이번 시간에 시간 복잡도가 알고리즘에 얼마나 많은 것을 보여주고 설명하는지를 알면 된다.
3. 점근표기식
우리가 어떤 나라가 잘살고 돈을 잘 버는지를 나타낼 때 대부분
GDP(국민 총 생산)를 말한다.
그 수치가 그 나라의 생산력을 가장 쉽게 이해시키기도 하면서 잘 나타내는 지표이기 때문이다.
알고리즘에도 그런 지표가 있다.
그것은 바로 점근 표기법이다.
점근 표기법은 얼마나 알고리즘이 빠르게 동작하는가 얼마나 좋은 성능을 갖고 있는가를 물을 때 수학적으로 표기하는 방법이다.
앞에서 설명한 N 정도의 시간과 공간이 걸리겠구나 하면서 분석했던 것이
점근 표기법의 일종이라고 말할 수 있다.
점근 표기법의 종류에는
빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표 기법이 있다.
빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지 이고
빅오 메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지에 대해 표기한다.
쉽게 말해 빅오는 최악 빅오 메가는 최선이다.
다음 알고리즘은 배열 내에 특정 숫자가 존재한다면 true, 아니면 false를 반환하는 알고리즘이다.
def is_number_exist(number, array):
for element in array: # array(N)의 길이만큼 아래 연산이 실행
if number == element: # 비교 연산 1번 실행
return True
return False
이 알고리즘은 N * 1의 시간 복잡도를 가진다.
그렇다면 모든 경우에 N만큼의 시간이 걸릴까?
우리가 만약 찾고자 하는 수가 배열에 맨 앞에 위치한다면
바로 true를 return하니까 1이라는 시간이 걸리고
찾고자 하는 수가 배열에 맨 뒤에 위치한다면
N 시간이 걸릴 것이다.
즉 최선은 1이고 최악은 N이다
이때 우리는 O(N), Ω(1)로 나타낼 수 있다.
근데 우리는 보통 어떤 알고리즘을 점근 표기법을 나타낼 때
빅오 표기법을 선호한다.
왜냐하면 대부분의 입력값이 최선의 경우일 가능성은 굉장히 적으며,
개발자는 최악의 경우를 대비해야 하기 때문이다.
'이론 > 알고리즘' 카테고리의 다른 글
| [알고리즘] DFS (Depth First Search) (0) | 2021.09.17 |
|---|---|
| [알고리즘] 병합정렬을 그림으로 알아보자 (0) | 2021.09.16 |
| [알고리즘] 버블정렬, 선택정렬, 삽입정렬 (0) | 2021.08.25 |
| [알고리즘] 재귀함수 (0) | 2021.08.21 |
| [알고리즘] 이진탐색 시간복잡도 (0) | 2021.08.21 |
