§ 1 · 메모리도 빅 오로공간에 적용된 빅 오
메모리가 제한적인 작은 하드웨어로 작업하거나, 대량의 데이터로 큰 메모리도 빠르게 채워질 때 — 공간 복잡도(space complexity)가 중요한 요소가 된다.
흥미롭게도 컴퓨터 과학자들은 시간 복잡도와 똑같이 빅 오로 공간 복잡도를 설명한다. 시간 빅 오가 "N개 데이터에 대한 연산 단계 수"였다면, 공간 빅 오는 "N개 데이터에 대해 알고리즘이 메모리에서 소비하는 추가 데이터 요소 수"다.
function makeUpperCase(array) { var newArray = []; for(var i = 0; i < array.length; i++) { newArray[i] = array[i].toUpperCase(); } return newArray; }
이 함수가 끝날 때 메모리에는 원본 배열과 똑같이 N개 요소를 가진 newArray가 떠 있다. 따라서 공간 복잡도는 O(N)이다.
§ 2 · 제자리 수정두 버전의 비교
더 메모리 효율적인 버전이 있다. 새 배열을 만들지 않고, 원본 배열의 각 문자열을 제자리에서(in place) 수정한다.
function makeUpperCase(array) { for(var i = 0; i < array.length; i++) { array[i] = array[i].toUpperCase(); } return array; }
| 버전 | 시간 복잡도 | 공간 복잡도 |
|---|---|---|
| 버전 1 (새 배열) | O(N) | O(N) |
| 버전 2 (제자리) | O(N) | O(1) |
두 버전 모두 시간은 O(N)이다. 그러나 버전 2는 추가 메모리를 전혀 쓰지 않으므로 공간이 O(1)이다. 이 경우 버전 2가 명백히 더 낫다.
§ 3 · 원본은 세지 않는다보조 공간
이 책에서 공간 복잡도는 보조 공간(auxiliary space)—추가로 소비하는 메모리—을 기준으로 판단한다. 원본 데이터는 세지 않는다.
§ 4 · 둘을 동시에 가질 수 없을 때시간과 공간의 트레이드오프
4장의 중복 검사를 다시 보자. 두 버전이 있었다.
- 버전 1(중첩 루프) — 추가 메모리를 쓰지 않는다. 시간 O(N²), 공간 O(1).
- 버전 2(보조 배열) — 원본 크기의 새 배열을 만든다. 시간 O(N), 공간 O(N).
| 버전 | 시간 복잡도 | 공간 복잡도 |
|---|---|---|
| 버전 1 (중첩 루프) | O(N²) | O(1) |
| 버전 2 (보조 배열) | O(N) | O(N) |
§ 5 · 마치며이 여정이 남긴 것
이 여정에서 우리는 자료구조와 알고리즘의 분석이 코드의 속도·메모리·우아함에 극적인 영향을 미친다는 것을 배웠다.
이 책이 준 것은 교육받은 기술 결정을 내리기 위한 틀이다. 빅 오 표기법이 한 접근이 다른 것보다 낫다고 시사할 수 있지만, 하드웨어의 메모리 구성이나 언어의 내부 구현 같은 다른 요소도 작용한다. 그래서 최적화는 항상 벤치마킹 도구로 측정하는 것이 가장 좋다 — 이 책의 지식이 방향을 가리키고, 벤치마킹이 올바른 선택을 확인해준다.
복잡하고 신비로워 보이는 이 주제들은 사실 더 쉬운 개념들의 조합일 뿐이며, 모두 당신이 이해할 수 있는 범위 안에 있다. 설명이 나빠서 어려워 보인다면 겁먹지 말고 더 나은 자료를 찾아라. 자료구조와 알고리즘의 세계는 넓고 깊으며, 우리는 겨우 표면을 긁었을 뿐이다. 행운을 빈다.