시간복잡도와 공간복잡도
이전 포스트에서 7가지 자료구조를 알아보았다.
이러한 자료구조들을 사용하면 컴퓨터에서 데이터를 더욱 빠르고 효율적으로 처리할 수 있고, 어떤 자료구조를 사용하느냐에 따라 프로그램의 성능이 크게 달라질 수 있다.
자료구조를 선택해야할 때 가장 크게 고려해야할 사항은 시간복잡도(Time complextity)와 공간복잡도(Space complexity)이다.
이 두 가지의 개념이 가장 중요한 이유는 코드의 효율성을 수치화하여 가장 잘 나타낼 수 있는 지표이기 때문이다.
빅오 표기법(Big-O)
빅오 표기법은 알고리즘을 수학적으로 표기해주는 표기법이다.
알고리즘의 시간과 공간 복잡도를 표현할 수 있다.
시간복잡도: 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다.
공간복잡도: 알고리즘이 실행될때 사용하는 메모리의 양을 나타낸다. (요즘에는 데이터를 저장할 수 있는 메모리의 발전으로 중요도가 낮아졌다.)
빅오 표기법은 알고리즘의 실제 러닝타임을 표기하는 것이라기 보다는 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 게 목표이기 때문에 상수와 같은 숫자들은 모두 1이 된다.
최대로 걸릴 수 있는 상한시간, 즉 최악의 경우(worst case)를 가장 먼저 고려하는 경우가 대부분이다.
이 때, 최악의 경우를 Big Oh라고 나타낸다.(Big Ω는 최선의 경우, Big Θ은 평균의 경우. 사실상 Bih Oh만 쓴다고 보면 됨.)
1. 공간 복잡도(Space complexity)
공간 복잡도란 프로그램이 실행되고, 완료되는데 필요한 메모리를 말한다.
프로그램을 실행하면, 데이터들이 RAM이라는 메모리에 올라가게 되는데, 이때 메모리의 크기는 고정이 되어있다.
즉, 메모리를 최대한 덜 잡아먹을 수 코드를 설계해야한다.
설계한 코드의 공간복잡도를 계산하는방법은 고정공간 요구량과 가변공간 요구량의 덧셈으로 구할 수 있다.
고정 공간 요구량(Fixed space requirements)
자료구조가 사용하는 고정된 메모리 공간을 의미한다.
고정된 크기를 갖는 변수(int, double)가 여기에 포함되며, 크기가 정해진 배열의 경우에도 고정 공간 요구량에 속한다.
가변 공간 요구량(Variable space requirements)
필요에 따라 동적으로 할당, 해제되는 메모리의 공간을 의미한다.
특정 instance에 따라서 사이즈가 달라지는 변수들이 여기에 속한다.
2. 시간 복잡도(Time complexity)
시간 복잡도란 프로그램이 실행되고, 완료되는데 걸리는 시간을 말한다.(이론적으로 계산할 수 있는)
시간 복잡도는 컴파일타임(Complie Time)과 러닝타임(Excution&Running Time)으로 나뉜다.
실행시간은 컴퓨터 사양이나, 네트워크 환경 등에 따라서 달라질 수 있는 부분이기 때문에 변수가 너무 많다. 그래서 우리는 컴파일 시간의 복잡도만 계산하면 된다.
for문으로 구구단을 1단부터 9단까지 나오게끔 코드를 짜면, 코드가 9 x 9 = 81번, 즉 9의 2승 만큼 실행이 된다.
그럼 N단이 나오는 코드를 짜면 어떤 값이 나올까? N^2의 값이 나올 것이다. 이렇게 사용하는 데이터 개수(N)에 의해서 시간복잡도가 정해진다.
*입력 N값에 따른 서로 다른 알고리즘의 시간복잡도(실행시간이 빠른순)
O(1) : 상수
아래 예제 처럼 입력에 관계없이 복잡도는 동일하게 유지된다.
1
2
def hello_world():
print("hello, world!")
O(N) : 선형
입력이 증가하면 처리 시간또는 메모리 사용이 선형적으로 증가한다.
1
2
3
def print_each(li):
for item in li:
print(item)
O(N^2) : Square
반복문이 두번 있는 케이스
1
2
3
4
def print_each_n_times(li):
for n in li:
for m in li:
print(n,m)
O(log n) O(n log n)
주로 입력 크기에 따라 처리 시간이 증가하는 정렬알고리즘에서 많이 사용된다.
다음은 이진검색의 예이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def binary_search(li, item, first=0, last=None):
if not last:
last = len(li)
midpoint = (last - first) / 2 + first
if li[midpoint] == item:
return midpoint
elif li[midpoint] > item:
return binary_search(li, item, first, midpoint)
else:
return binary_search(li, item, midpoint, last)
시간복잡도를 구하는 요령
각 문제의 시간복잡도 유형을 빨리 파악할 수 있도록 아래 예를 통해 빠르게 알아 볼수 있다.
하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)
컬렉션 정렬을 사용하는 경우 : O(n*log(n))
자료구조 비교
📑 참고 자료