[알고리즘] 알고리즘의 성능은 어떻게 표현할까? | 알고리즘 성능 정리

 

알고리즘의 성능은 시간 복잡도(Time complexity)와 공간 복잡도 (space complexity)로 표현한다.

 

시간 복잡도는 입력 값의 개수와 처리 시간과의 관계를 표현하고,

공간 복잡도는 입력 값의 개수와 메모리 증가량과의 관계를 표현한다.

 

시간 복잡도는 입력 값의 개수와 알고리즘의 처리 시간과의 상관관계를 표현한 말로

입력 데이터의 양이 많아짐에 따라 처리 속도가 어떻게 변화하는지를

수학의 기호를 빌려 표현하는 방식이다.

 

쉽게 생각해서 수학의 방정식을 떠올리면 된다.

 

x축을 입력 값의 개수로 놓고 y축을 처리 시간으로 봤을 때,

x가 증가함에 따라 y가 어떻게 변화하는지를 표현하는 것이다. 

 

x와 y가 일정한 비율로 증감한다면 선형(linear) 시간 복잡도를 가진다고 표현하며,

지수나 로그의 형태로 증가한다면 각각 지수형, 로그형 시간 복잡도를 가지고 있다고 표현한다.

 

공간 복잡도 역시 기본적으로 시간복잡도와 동일하다.

다만 처리 시간 대신 메모리의 사용량 변화를 비교하는 것만 다를 뿐이다.

 

예를 들어 어떤 탐색 알고리즘의 입력 데이터 개수가 100개에서 1000개로 증가할 때

탐색 시간이 선형적으로 증가한다면 이 알고리즘은 선형 시간 복잡도를 가지고 있다고 얘기한다.

 

입력 데이터가 100개에서 1000개로 증가하더라도 처리 시간에 변화가 없다면

이 알고리즘은 상수 시간 복잡도를 가지고 있다고 말한다.

 

알고리즘의 성능은 보통 빅오 표기법(big O)으로 표현한다.

O(n) 표기법으로 불리기도 한다.

이 알고리즘은 최악의 상황에서도 이 성능 이상을 보장한다는 의미이다.

 

O(n) 표기법에서 괄호 안의 n은 입력 데이터의 개수를 의미한다.

O(n) 표기법으로 성능을 표현할 때, 괄호 안에는 입력 데이터의 개수 n에 대한 알고리즘 처리 시간을 표기한다.

즉 O(n)은 n개의 입력이 들어올 경우 처리도 n번 수행한다는 의미로 받아들이면 된다.

 

O(n2) <제곱> 은 n개의 입력을 처리하기 위해 코드를 n제곱번 수행하는 것이다.

그러므로 O(n2)은 입력 데이터의 양이 증가할 때 처리 시간은 입력 데이터 증가량의 제곱에 비례한다는 뜻이다.

 

O(1)은 n의 크기와 상관없이 항상 고정된 시간이 걸린다는 뜻이다.

 

다음은 알고리즘의 표기표다.

 

 

알고리즘 표기표

 

시간 복잡도에 따른 성능을 그래프로 그리면 다음과 같다.

 

 

시간복잡도의 성능 그래프

시간복잡도의 성능 순서를 표현하자면 아래와 같다.

 

O(1) > O(log2n) > O(√n) > O(n) > O(n log2 n) > O(n2) > (O2n) > O(n!)

 

O(n!) 같은 경우는 외판원 문제로

현재까지 나온 컴퓨터 성능으로도 쉽게 풀지 못하는 문제라고 한다.

 

 

이제 수많은 데이터가 네트워크 공간에서 돌아다니고

그 데이터가 하나의 플랫폼과 생태계가 만들어지는 재료가 되는만큼

 

프로그램이 처리 속도를 뒷받침 하지 못한다면 앞날이 암담하다.

 

이게 알고리즘을 공부해야 하는 이유일 것이다.