[Algorithm] 1. 시간 복잡도, 공간 복잡도

[Algorithm] 1. 시간 복잡도, 공간 복잡도

 

 

1. 복잡도란?

알고리즘의 성능을 나타내는 척도

얼마나 복잡한지를 의미한다. 높아질 수록 좋지는 않은 것이다.

알고리즘은 컴퓨터 속에서 돌아간다. 그렇기 때문에 얼마나 더 오래 걸리느냐, 얼마나 더 큰 용량을 차지하느냐로 복잡도를 계산한다.

이를 각각 시간 복잡도, 공간 복잡도라고 한다.

 

시간 복잡도와 공간 복잡도는 일종의 거래 관계에 있다.

마치 역세권을 희망하면 월세가 높아지고, 월세를 낮추려면 역세권을 포기해야 하는 것처럼

메모리를 더 사용하는 대신 시간을 줄일 수도 있고 시간을 더 쓰는 대신 메모리 용량을 작게 사용할 수 있다.

 

이 계산은 우리가 유한한 성능을 가진 컴퓨터와 기기들을 가지고 있기 때문에, 효율적이고 더 빠르고, 더 경제적인 프로그램을 만들기 위해서 존재한다. 단순히 코드를 따라쓰고, 함수를 만들어내서 어떤 프로그램을 만들어낼 수는 있다. 하지만, 돌아가는 것과 효율적으로 돌아가는 것에는 차이가 있는 법. 더 나은 프로그램, 효율적이고 경제적이며 아름다운 프로그램을 만들기 위해서는 반드시 복잡도를 고려하고 설계와 건설이 들어가야 할 것이다.

 

2. 시간 복잡도

알고리즘을 위해 필요한 연산의 '횟수'

횟수가 증가하면 시간 복잡도가 증가한다.

시간 복잡도를 표현할 때는 '빅오 표기법'을 사용한다.

가장 빠르게 증가하는 항만을 고려하는 표기법이다.

 

반복문 for문의 경우, 5번의 반복을 한다고 하면, 그 반복문이 들어있는 py 파일 전체가 실행되는 것에 있어 일단 5번의 반복 연산은 무조건 하게 되어있다. 이렇듯 연산의 횟수를 기준으로 해서 빅오 표기를 하고 이에 따라 상수 시간, 로그 시간, 선형 시간 등의 시간 복잡도를 표기하는 것이다.

 

빅오 표기법에 따른 각각의 시간 명칭은 다음과 같다.

빅오 표기법	명칭
O(1)	상수시간(Constant time)
O(logN)	로그시간(Log time)
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N²)	이차시간
O(N³)	삼차시간

이외에도 지수시간, 팩토리얼 시간 등이 있는데, 아직 한 번도 사용하거나 본적이 없다.

아래로 내려올 수록 복잡도가 높아진다고 볼 수 있다. n이 커짐에 따라 값도 가파르게 증가함을 알 수 있다.

 

빅오 표기법에서는 차수가 가장 큰 항만 남기고 나머지는 무시한다.

연산횟수가 3N²+5N 인 횟수가 있을 때, 이차 시간만을 두고 시간복잡도를 계산하는 것이다.

 

 

++

시간 복잡도에서의 '연산'은 프로그래밍 언어에서 지원하는 사칙 연산, 비교 연산 등과 같은 기본 연산을 의미한다. 예를 들어 두 정수 a와 b를 더하는 더하기 연산뿐만 아니라, 두 정수 a와 b의 값을 비교하는 비교 연산 또한 한 번의 연산으로 취급한다.

 

 

3. 공간 복잡도

알고리즘을 위해 필요한 메모리의 '양'

필요한 메모리의 양이 많을 수록 공간 복잡도가 증가한다.

 

숫자 자료형 int를 가진 배열을 예시로 들어보면 공간 복잡도는 다음과 같다.

a[1000] : 4KB

a[1000000] : 4MB

a[2000][2000] : 16MB

 

알고리즘 문제를 풀 때 만약 데이터의 개수가 1,000만 단위가 넘어가면 메모리 초과를 생각해야 한다.

예를 들어 계수 정렬의 경우, 1~1,00만 까지의 계수를 세기 위해 계수를 세는 배열을 생성하면 4MB의 메모리가 사용된다.