속도만큼 중요한 메모리 공간
크리스는 지난번에 배운 시간 복잡도(O) 개념을 활용해 코드를 최적화했다. 25억 번의 연산을 10만 번으로 줄여서 속도를 획기적으로 높였다.
"이제 완벽해! 속도가 비행기야."
그런데 배포 후 며칠 뒤, 사용자에게서 이상한 제보가 들어왔다.
"쇼핑몰 탭만 열어두면 크롬이 메모리를 2GB나 잡아먹고, 결국엔 '앗, 이런!' 하면서 탭이 죽어버려요."
속도는 빨라졌지만, 이번엔 메모리(RAM)가 문제였다. 크리스는 데이터를 빠르게 찾기 위해 너무 거대한 객체를 만들었고, 재귀 함수를 깊게 파고들다가 브라우저의 메모리 한계를 넘겨버린 것이다.
알고리즘의 성능은 속도(시간)뿐만 아니라, 공간(메모리)으로도 평가받는다. 이것이 바로 공간 복잡도(Space Complexity)다.
1. 공간 복잡도란?
시간 복잡도가 "데이터가 늘어날 때 시간이 얼마나 더 걸리는가?"라면,
공간 복잡도는 "데이터가 늘어날 때 메모리를 얼마나 더 차지하는가?"를 나타낸다.
우리가 작성하는 코드는 크게 두 가지 공간을 사용한다.
알고리즘 성능을 논할 때는 주로 보조 공간을 얼마나 쓰느냐가 핵심이다.
2. 변수 하나는 가볍다: O(1)
가장 효율적인 공간 복잡도다. 입력 데이터가 100만 개라도, 추가로 사용하는 공간은 변수 몇 개뿐인 경우다.
// ✅ 공간 복잡도 O(1)
function sum(arr) {
let total = 0; // 변수 하나 (숫자 타입)
for (let i = 0; i < arr.length; i++) {
total += arr[i]; // 기존 공간 재사용
}
return total;
}arr의 크기가 아무리 커져도, total과 i 변수 딱 두 개만 더 필요하다. 메모리 효율이 아주 좋다.
3. 복사하면 무거워진다: O(N)
입력 데이터와 비례해서 공간이 필요해지는 경우다. 보통 배열을 복사하거나, 결과를 담을 새로운 배열을 만들 때 발생한다.
// ⚠️ 공간 복잡도 O(N)
function double(arr) {
const newArr = []; // 입력(arr)만큼의 공간이 새로 필요함
for (let i = 0; i < arr.length; i++) {
newArr.push(arr[i] * 2);
}
return newArr;
}만약 arr가 100MB짜리 데이터라면, newArr도 100MB를 차지한다. 순식간에 메모리 사용량이 2배가 된다. 자바스크립트의 map, filter, slice 등은 모두 새로운 배열을 반환하므로 공간 복잡도는 $O(N)$이다.
(참고: 자바스크립트에서 문자열(String)은 불변(Immutable)이므로, 문자열을 더하거나(+) 자를 때마다 새로운 메모리 공간이 할당된다. 문자열 조작도 O(N) 공간을 쓸 수 있음을 명심하자.)
4. 숨겨진 비용: 재귀 함수의 스택 메모리
크리스가 가장 놓치기 쉬운 부분이 바로 여기다. 변수를 선언하지 않았는데 메모리가 터지는 경우다.
// ❌ 공간 복잡도 O(N) - 재귀 호출
function countdown(n) {
if (n <= 0) return;
console.log(n);
countdown(n - 1); // 자기 자신을 호출
}
countdown(50000); // Maximum call stack size exceeded함수가 종료되지 않고 또 다른 함수를 호출하면, 컴퓨터는 돌아올 위치를 기억하기 위해 '호출 스택(Call Stack)'이라는 메모리 공간에 기록을 남긴다.
재귀가 N번 깊어지면, 스택 메모리도 N개만큼 쌓인다.
따라서 재귀 함수는 코드상으로 변수가 없어 보여도, 보이지 않는 곳에서 O(N)의 공간을 소비한다. 이를 해결하려면 재귀를 반복문(for, while)으로 바꿔야 한다. 반복문은 스택을 쌓지 않으므로 공간 복잡도가 O(1)이다.
5. 트레이드오프(Trade-off): 시간과 공간의 거래
재미있는 점은, 시간 복잡도와 공간 복잡도는 종종 반비례 관계(Trade-off)에 있다는 것이다.
크리스가 첫 번째 글에서 썼던 Set을 기억하는가?
Set을 만들면서 메모리(O(N) 공간)를 추가로 사용했지만, 그 대가로 검색 속도(O(1) 시간)를 얻었다.
현대의 개발 환경은 램(RAM)이 넉넉한 편이라, 보통은 메모리를 조금 희생해서라도 속도를 높이는 쪽을 택한다. 하지만 모바일 환경이나 대용량 데이터 처리에서는 메모리 절약이 필수적이다.
핵심 정리
이제 시간과 공간, 두 가지 무기를 모두 갖췄다.
마지막으로 이 모든 지식을 종합해서, 내 코드를 보고 "이건 O(N)이고 저건 O(1)이네"라고 분석할 수 있는 실전 훈련을 해보자.
다음으로는 “코드를 빅오 표현법으로 표현하기: 실전 예제 풀이" 편에서 계속된다.