복잡도는 알고리즘 성능을 나타내는 척도이다. 크게 시간복잡도와 공간복잡도로 나눠볼 수 있으며, 각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시한다.
일반적으로 시간복잡도와 공간복잡도는 trade-off관계에 있다. 즉, 시간복잡도를 줄이려면 공간복잡도(메모리 사용량)가 늘어나고, 공간복잡도를 줄이려면 시간복잡도가 늘어나는 그런 관계라는 뜻이다.
시간복잡도(Time Complexity)
작성한 알고리즘 코드가 입력값에 비례해서 어느정도의 연산량을 필요로 하는지 그 연산횟수를 말한다.(알고리즘 필요 연산 횟수)
시간 복잡도(Time Complexity)는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을 수행하는 데 연산들이 몇 번 이루어지는 지를 숫자로 표기한다.
시간복잡도 계산에는 Best Case(빅오메가), Average Case(빅세타), Worst Case(빅오)가 있지만 일반적으로 시간복잡도의 척도를 계산할 때는 Worst Case(최악의 경우)를 주로 사용한다. 여기서 최악의 경우를 계산하는 방식을 빅오 표기법(Big-O notation)이라고 한다. 시간 복잡도 함수에서 상대적으로 불필요한 연산을 제거하여 알고리즘의 분석을 조금 더 간편하게 할 목적으로 시간 복잡도를 표기하는 방법이다.
| 복잡도 | 시간 | 설명 | 예시 |
| O(1) | 상수 시간 | n의 크기에 상관없이 일정 | 스택(push, pop), 인덱싱 |
| O(log n) | 로그 시간 | 데이터 크기가 커질수록 처리시간이 로그만큼 짧아진다. 입력값 n에 대해 log n 만큼의 연산이 이루어진다는 의미이다. | 이진 트리(binary tree) |
| O(n) | 선형 시간 | 데이터 크기에 비례해 커진다. 데이터가 10배가 되면 처리시간도 10배가 된다는 뜻 | for 문 |
| O(n log n) | 로그 선형 시간 | 데이터 크기가 커질수록 처리시간이 로그배만큼 길어다. 데이터가 10배면 처리시간도 20배로 늘어나는 느낌. | 퀵 정렬(quick sort), 병합 정렬(merge sort), 힙 정렬(heap sort) |
| O(n^2) | 이차 시간 | 데이터가 많아질수록 처리시간도 급수적으로 늘어나는 것이다. | 이중 for문, 삽입 정렬(Insertion sort), 거품 정렬(bubble sort), 선택 정렬(selection sort) |
| O(2^n) | 지수 시간 | 데이터가 많아질수록 처리시간이 기하급수적으로 늘어나는 것이다. | 피보나치 수열 |
빅오 표기법 시간복잡도와 그 예시이다. O(1)이 가장 복잡도가 낮은 것이다. 위로 갈수록 복잡도가 낮아진다.
공간복잡도(Space Complexity)
공간복잡도는 그 알고리즘 코드가 필요로 하는 메모리의 정도를 나타내는 것이다. (알고리즘 필요 메모리) 요즘엔 메모리 성능이 좋아져서 별로 고려하지 않아도 된다고 한다. 그래서 요즘에는 공간을 좀더 쓰더라도 시간복잡도를 줄이는 방향으로 나아가고 있다고 한다.
총 공간 요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있다.
고정 공간은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)를 말한다.
가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간, 그러니까 동적으로 필요한 공간을 말한다.
공간 복잡도 역시 시간 복잡도 처럼 보통 최악의 경우를 따져 Big-O notation으로 그 복잡도를 판단하게 된다.
가령 크기가 n인 배열을 입력했는데, 알고리즘이 내부에서 n * n 의 이차원 배열을 생성한다면 이 알고리즘의 공간 복잡도는 n^2 가 된다.
공간 복잡도는 보통 시간 복잡도보다 중요하게 생각되지 않는 경우가 많지만 빅데이터 처리를 하는 경우, 공간 복잡도가 위와 같이 커지게 된다면, 메모리에 한 번에 올라가지 않아 프로그램을 실행할 수 없는 문제가 발생할 수 있다. 이 경우, 데이터를 나눠서 처리하고 다시 합치는 방법을 사용하게 된다.
알고리즘 작성 시, 공간 복잡도를 아예 생각하지 않으면 위험할 수 있으므로 공간 복잡도도 신경써서 작성해 주자.
아래는 이제부터 공부할 자료구조별 시간복잡도, 정렬 알고리즘별 시간복잡도이다. 익숙해지도록 하자.
