[알고리즘] 시간 복잡도와 공간 복잡도의 이해와 빅오(Big-Oh) 표기법

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)

설계를 하고 코딩을 한다음 기능이 잘 동작하는 것은 물론이지만 좋은 성능까지 보장받기를 원한다. 때문에 우리는 자료구조와 알고리즘을 분석하고 평가할 수 있어야 한다. 

평가는 2가지로 할 수 있다. 하나는 속도에 관한것(시간 복잡도) 다른 하나는 메모리 사용량(공간 복잡도)이다.

 

옛날에는 하드웨어가 안좋았기 때문에 메모리 사용량을 많이 고려했었지만 지금은 하드웨어가 매우 좋기 때문에 메모리 사용 보다는 실행속도에 초점을 둔다.  

 

실행속도를 평가하기 위해 조건마다 다르게 실행해가면서 수행시간을 평가할 수는 없다. 그래서 수행시간을 재기 위해 연산의 횟수를 통해서 알고리즘의 빠르기를 판단해야 한다. 그러기 위해서는 데이터의 수를 함수에 입력하면 연산의 횟수가 바로 계산이 되는 식을 만들어야 한다.

즉 알고리즘 별 연산횟수를 함수 T(n)의 형태로 구성하면 아래 그림 같이 그래프를 통해 데이터의 수와 변화에 따른 연산횟수의 변화 정도를 한눈에 파악할 수 있다. 이래서 둘 이상의 알고리즘을 비교하기가 용이해진다.

알고리즘 수행속도 비교

위 알고리즘에서 확인할 수 있는건 데이터 수가 적으면 알고리즘 B가 좋지만 데이터 수가 많으면 알고리즘 A가 좋다. 그래서 어떤 알고리즘을 사용해야 하는지는 상황에 맞게 답을 내려야 하는 것이다. 

 

빅오 표기법(Big-Oh Notation)

빅오 표기법을 구하려면 먼저 T(n)에 대한 함수를 구하여야 한다. T(n)에 대한 함수의 식은 간단하다 상수항은 수행 라인수 1차함수는 반복문 2차함수는 2중 반복문 이런식으로 표기가 된다. 만약 함수 T(n) 식이 n^2 + n + 1 이면 이중반복문 + 반복문 + 수행라인수1 인 것이다.

 

T(n) = n^2 + n + 1 함수에서 n이 증가할수록 n^2이 차지하는 비율이 커진다. n이 무한대로 커질수록 n^2 의 비율이 99프로를 차지하기 때문에 T(n) = n^2로 간략히 표기 할 수 있고 이것을 빅오 표기법으로 바꾸면 O(n^2) 이 된다.

 

빅오는 대표적으로 O(1), O(logn), O(n), O(nlogn), O(n^2), O(2^n) 이 있고 수행시간 비교는 아래 사진으로 보듯이 데이터가 많아질수록 O(2^n)이 가장 수행시간이 길고, O(1)이 가장 작다. 만약 T(n) 함수에 n과 nlogn이 같이 있다면 빅오는 당연히 O(nlogn)이 된다.

 

 

참고

윤성우의 열혈 자료구조