시간 복잡도와 공간 복잡도가 등장한 이유
시간 복잡도와 공간 복잡도는 어떤 알고리즘이 더 효율적인지 분석하기 위해 탄생한 개념입니다.
컴퓨터는 연산 속도와 메모리에 한계가 있기 때문에 같은 문제를 풀더라도 더 빠르고 메모리를 적게 사용하는 방법을 찾는 것이 중요합니다.
초기 컴퓨터는 연산 성능이 낮고 저장 공간이 부족했기 때문에 프로그래머들은 어떤 알고리즘이 실행 속도가 빠른지, 얼마나 많은 메모리를 사용하는지 분석하는 방법을 연구해 왔습니다.
이 과정에서 시간 복잡도와 공간 복잡도를 정의하고, 알고리즘을 빅오 표기법(Big-O Notation)으로 표현합니다.
1. 시간 복잡도(Time Complexity)
프로그램이 올바르게 실행되는 것도 중요하지만, 빠르게 실행되는 것이 더욱 중요합니다.
알고리즘을 잘못 선택하면 입력 크기(N)가 커질수록 실행 속도가 급격히 느려질 수 있습니다.
아래 그림과 같이 입력 크기가 커질수록 O(1) < O(log N) < O(N) < O(N²) 순으로 실행 시간이 증가하는 것을 볼 수 있습니다.
즉, O(N²)과 같은 높은 시간 복잡도를 가지는 알고리즘보다는, O(1)과 같은 효율적인 알고리즘을 지향하는 것이 좋습니다.
우리가 알고리즘을 개선하여 속도를 향상시키려면, 내가 작성한 알고리즘의 시간 복잡도를 계산할 수 있어야 합니다.
시간 복잡도를 계산하는 방법을 다음 예제를 통해 살펴보겠습니다.
예제: 시간 복잡도 분석
for (int i = 0; i < 10; i++) { // 10번 반복 (상수 시간)
for (int j = 0; j < n; j++) { // n번 반복
for (int k = 0; k < n; k++) { // n번 반복
if (true) cout << k << '\n'; // O(1) 연산
}
}
}- 첫 번째 for문 (i = 0; i < 10; i++): 10번 반복 (상수 개수)
- 두 번째 for문 (j = 0; j < n; j++): n번 반복
- 세 번째 for문 (k = 0; k < n; k++): n번 반복
즉, 전체 반복 횟수는: 10 × n
하지만, 빅오 표기법에서는 상수 계수(10)를 무시하므로, 이 알고리즘의 시간 복잡도는 O(n²)가 됩니다.
2. 공간 복잡도(Space Complexity)
공간 복잡도는 알고리즘이 실행될 때 사용하는 메모리의 양을 분석하는 개념입니다.
컴퓨터의 메모리는 한정되어 있기 때문에, 같은 문제를 해결할 때 더 적은 메모리를 사용하면서도 효율적인 알고리즘을 선택하는 것이 중요합니다.
특히 임베디드 시스템, 모바일 앱, 서버 시스템 등에서는 메모리 최적화가 필수적입니다.
공간 복잡도를 분석함으로써, 알고리즘이 실행되는 동안 얼마나 많은 추가 메모리를 소비하는지 평가할 수 있습니다.
공간 복잡도의 구성 요소
공간 복잡도는 크게 두 가지 요소로 구성됩니다.
- 고정 공간(Fixed Space, O(1))
- 입력 크기와 관계없이 항상 일정한 공간을 사용하는 경우입니다.
- 예: 변수, 상수, 고정된 크기의 배열 또는 객체
- 가변 공간(Variable Space, O(N) 이상)
- 입력 크기에 따라 사용하는 메모리 공간이 증가하는 경우입니다.
- 예: 동적 배열, 재귀 호출 스택, 추가적인 데이터 구조(HashMap, Graph 등)
예제: 공간 복잡도 분석
void example(int n) {
int a = 0; // O(1) - 변수 1개
int arr[100]; // O(1) - 고정 크기의 배열
vector<int> dynamicArr(n); // O(n) - 입력 크기에 따라 동적 메모리 사용
for (int i = 0; i < n; i++) {
cout << dynamicArr[i] << '\n';
}
}공간 복잡도 분석 과정
- 고정 공간 (O(1))
- int a = 0; → 단일 변수는 O(1)
- int arr[100]; → 크기가 변하지 않는 배열도 O(1)
- 가변 공간 (O(n))
- vector<int> dynamicArr(n); → 입력 크기 n에 비례하는 O(n) 만큼의 추가 공간 사용
따라서, 이 코드의 전체 공간 복잡도는 O(n) 입니다.