공간 복잡도 쉽게 이해하기
문제 상황
개발을 하다 보면, 시간 복잡도에만 신경 쓰는 경우가 많다.
나도 예전에 알고리즘 문제를 풀 때 항상 실행 시간이 얼마나 걸리는지만 봤지, 메모리를 얼마나 쓰는지는 잘 생각하지 않았다.
근데 한 번은 프로덕션 서버에서 대용량 데이터를 처리하는 로직을 짜다가, 아무리 성능이 빨라도 메모리 사용량이 터져서 OOM(Out Of Memory) 이 나버린 적이 있었다.
그때 느꼈다.
아무리 시간이 빨라도, 메모리를 무지막지하게 쓰면 서비스가 뻗어버린다는 걸.
그래서 오늘은 공간 복잡도가 무엇인지, 왜 중요한지, 어떻게 계산하는지 얘기해 보려고 한다.
내가 처음 공부할 때 이해하기 어려웠던 부분을 최대한 풀어 써볼게.
내가 시도한 방법
처음에 공간 복잡도를 배우려고 했을 때, 정의만 보면 좀 딱딱했다.
"공간 복잡도(Space Complexity)란, 알고리즘이 실행될 때 필요한 메모리 공간의 양을 입력 크기(n)에 따라 표현한 것이다."
이렇게만 들으면 뭔가 와닿지 않았다.
그래서 시간 복잡도를 공부할 때처럼, 일단 코드 예제에 직접 대입해 보기로 했다.
또, 무조건 "O" 표기로 외우지 않고, 어떤 것들이 공간에 영향을 주는지 구분해보기로 했다.
이렇게 구분하면 이해하기 더 쉬웠다
- 입력 공간(Input Space): 함수 인자로 들어오는 데이터가 차지하는 공간
- 보조 공간(Auxiliary Space): 알고리즘이 추가로 사용하는 공간 (임시 변수, 재귀 스택 등)
- 총 공간: 입력 공간 + 보조 공간
이 구분법을 머리에 두고 코드를 읽으면, "아, 이건 입력 데이터니까 별도 저장 안 하면 추가 공간은 안 드는구나", "이건 배열을 새로 만들어서 보조 공간이 필요하구나" 하는 식으로 감이 오더라.
해결 과정 및 코드 예시
아래 예시 코드를 보면서 같이 공간 복잡도를 따져보자.
// 예시 1: 단순 반복문
public int sum(int[] arr) {
int total = 0;
for (int num : arr) {
total += num;
}
return total;
}
이 코드는 입력 배열 arr의 크기를 n이라고 하면:
- 입력 공간: O(n) (배열 자체)
- 보조 공간: O(1) (total 변수 하나만 필요)
- 총 공간 복잡도: O(n)
여기서 핵심은 보조 공간이 상수라는 점이다. 즉, 아무리 배열이 커도 추가로 메모리를 많이 쓰지 않는다.
다음은 조금 더 복잡한 예제다.
// 예시 2: 새로운 배열 생성
public int[] duplicateArray(int[] arr) {
int n = arr.length;
int[] newArr = new int[n];
for (int i = 0; i < n; i++) {
newArr[i] = arr[i];
}
return newArr;
}
여기서는:
- 입력 공간: O(n)
- 보조 공간: O(n) (newArr 배열)
- 총 공간 복잡도: O(n)
이 경우에는 입력 데이터 외에 동일 크기의 배열을 하나 더 생성하므로 메모리가 두 배로 든다.
실무에서는 이런 부분이 대규모 데이터 처리에 꽤 큰 영향을 미친다.
나도 로그 데이터 처리할 때 비슷한 실수를 해서 JVM 힙을 터트린 적이 있었다.
마지막으로 재귀를 볼까?
// 예시 3: 재귀 호출
public int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
여기서는:
- 입력 공간: O(1) (n 하나만 인자로 전달)
- 보조 공간: O(n) (재귀 호출 스택)
- 총 공간 복잡도: O(n)
재귀 함수의 큰 특징은 호출 스택이 쌓인다는 것이다.
그래서 n이 커지면 메모리도 같이 증가한다.
이 부분을 간과하면 StackOverflowError가 난다.
나도 옛날에 피보나치 수열을 재귀로 짰다가 n=100에서 바로 뻗었던 기억이 있다.
정리 및 느낀 점
공간 복잡도를 공부하고 직접 코드를 대입해 보면서 느낀 건 딱 하나였다.
시간 복잡도만큼 공간 복잡도도 중요하다는 거다.
특히 실무에서는
- 대용량 데이터를 처리할 때
- 비동기로 많은 작업이 동시에 돌 때
- 캐싱을 과도하게 사용할 때
메모리가 금방 바닥나 버린다.
정리하자면, 공간 복잡도를 볼 땐 아래 세 가지를 항상 따져보자
- 입력 데이터가 차지하는 공간은 얼마나 되는지?
- 추가로 생성되는 보조 공간은 어느 정도인지?
- 재귀나 내부 로직 때문에 스택이나 큐가 얼마나 쌓이는지?
내가 겪었던 문제를 다시 생각해보면, 코드만 봐서는 잘 드러나지 않던 메모리 이슈가 많았다.
그래서 앞으로는 새 기능을 개발할 때 시간과 공간 복잡도를 같이 계산하는 습관을 들이려고 한다.
혹시 나처럼 공간 복잡도가 헷갈리는 분들이 있다면, 꼭 코드에 직접 대입해보고 하나씩 구분해 보는 걸 추천한다.