시간복잡도 / 공간복잡도

이름만 들으면 벌써부터 머리가 아파올 것이다.

시간, 공간이라는 단어가 주는 압박감에서부터 복잡도라는 키워드를 들으니 우선적으로 수학을 잘해야할 것 같은 느낌과 함께 어려운 개념이라는 느낌이 우선적으로 들기 때문이다.

 

차근차근 알아보자.

---

우선, 복잡도라는 개념은 개발자들이 구현한 알고리즘의 성능을 평가하기 위한 용도로써 기준이 되는 개념이라고 보면 될 것 같다.

그 중에서 중요하다고 생각되는 것이 시간복잡도, 공간복잡도이다.

복잡도라는 이름만 들어도 생각할 수 있는 것이 복잡도가 낮을 수록 좋은 알고리즘이라는 것이다.

 

 

※ 시간복잡도

시간복잡도는 특정 알고리즘이 수행되기까지 걸리는 시간 혹은 횟수를 의미한다.

같은 결과를 가지게 되는 여러 프로그래밍 코드에서도 작성 방법에 따라 걸리는 시간이 달라지며, 이왕 같은 결과를 도출해낸다고 한다면 복잡도가 낮은 것이 당연히 좋은 알고리즘이다.

 

[빅-오 표기법]

시간 복잡도에는 빅-오 표기법이라는 개념이 존재한다.

예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기 할 때 운이 좋으면 1번에 뒷면이 나오지만 운이 안 좋다면 n번 만큼 동전을 튕겨야 하는 경우가 발생한다.

이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라 부른다.

 

# 시간 복잡도 그래프

 

※ 여기서 n이란 입력되는 데이터를 의미한다.

O(1) (Constant)

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타낸다.

데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않는다.

 

O(log₂ n) (Logarithmic)

입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘이다.

예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 된다..

이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당된다.

 

O(n) (Linear)

입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘이다.

예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 된다.

대표적으로 1차원 for문이 있다.

 

O(n log₂ n) (Linear-Logarithmic)

데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘이다.

예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다.

정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적이다.

 

O(n²) (quadratic)

데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘이다.

예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 된다.

이중 루프(n² matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직하다.

 

O(2ⁿ) (Exponential)

데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘이다.

대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당된다.

 

그래프와 위 설명을 참고하여, 시간 복잡도에 따른 성능을 비교하면 아래와 같다.

faster O(1) < O(log n) < O(nlog n) < O(n²) < O(2ⁿ) slower

slower로 갈수록(즉, 오른쪽 방향으로 갈수록) 효율성이 떨어진다.

 

 

※ 공간복잡도

공간복잡도는 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐에 대한 척도이다.

 

공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 얼마 만큼의 동적 할당인지, 몇 번의 호출을 하는 재귀 함수인지 등이 공간 복잡도에 영향을 끼친다.

프로그램에 필요한 공간은 크게

1. 고정 공간
2. 가변 공간

이 있는데, 시간적인 측면을 무시하고 공간 복잡도만 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료 구조가 더 효율적이다.

함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요하다.

특히, 재귀 함수의 경우 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소를 저장할 공간이 필요해서 재귀적(Recursive)으로 짤 수도 있고, 반복문으로도 짤 수 있는 경우에는 반복문으로 짜는 것이 더 효율적이라고 생각한다.