공간 복잡도

공간 복잡도는 입력이 커질 때 코드가 쓰는 메모리가 얼마나 빨리 불어나는지 알려 줍니다. 메모리를 바이트로 재지 않습니다. 값을 몇 개 담아 두는지 세어서 그 수가 늘어나는 꼴을 봅니다. 그래서 데이터가 많아져도 메모리가 모자라지 않을 방법을 미리 고를 수 있습니다.

쉽고 빠른 이해

공간 복잡도는 데이터가 늘 때 코드가 쓰는 메모리가 어떤 꼴로 늘어나는지 알려 줍니다. 목록의 합계만 구하는 코드는 목록이 백 배로 커져도 합계를 담을 변수 하나면 됩니다. 목록을 복사해 두는 코드는 목록이 두 배가 되면 메모리도 두 배로 씁니다.

이게 없으면 개발 환경에서 멀쩡하던 코드가 운영 데이터를 한꺼번에 불러오다 메모리가 바닥나는 것을 미리 알 수 없습니다.

이렇게 셉니다.

입력의 크기를 n 이라고 둔다
코드가 입력 말고 더 담아 두는 값이 몇 개인지 n 으로 적는다
n 이 아주 커질 때 가장 빨리 자라는 부분만 남긴다

대가도 있습니다. 값 하나가 몇 바이트인지는 버립니다. 그래서 메모리를 몇 메가바이트 쓰는지는 따로 재 봐야 합니다.

상세

선생님이 시험지 백 장을 채점한다고 해 봅시다. 반 평균만 내면 된다면 점수를 더해 가며 메모지에 합계 한 줄만 고쳐 쓰면 됩니다. 등수까지 매기려면 학생마다 점수를 한 줄씩 적어 두어야 합니다. 학생이 두 배로 늘면 메모지도 두 배로 듭니다.

공간 복잡도는 이 차이를 적는 방법입니다. 코드나 알고리즘 하나가 메모리를 몇 바이트 쓰는지는 묻지 않습니다. 다룰 데이터가 늘어날 때 쓰는 메모리가 어떤 꼴로 늘어나는지를 묻습니다. 걸리는 시간을 같은 방식으로 세는 잣대는 시간 복잡도입니다. 둘은 대개 함께 적습니다.

이 절은 무엇을 세는지부터 공간 복잡도가 알려 주지 않는 것까지 차례로 봅니다.

입력 크기와 메모리 칸

공간 복잡도를 세려면 먼저 입력 크기를 정합니다. 목록의 원소 수나 문자열의 길이처럼 다룰 데이터의 양을 나타내는 수입니다. 이 수를 n 이라고 부릅니다.

다음으로 메모리를 세는 단위를 정합니다. 수 하나, 문자 하나, 다른 값을 가리키는 참조 하나처럼 크기가 입력과 상관없이 정해진 값 하나를 한 칸으로 봅니다. 한 칸이 몇 바이트인지는 따지지 않습니다.

바이트 대신 칸을 세는 까닭은 바이트가 언어와 기계마다 다르기 때문입니다. 같은 정수 하나도 언어에 따라 차지하는 바이트가 다릅니다. 칸의 개수는 어디서 돌려도 같습니다. 그래서 방법끼리 견줄 잣대가 됩니다.

마지막으로 언제의 칸 수를 셀지 정합니다. 코드가 도는 동안 쥐고 있는 칸 수는 오르내립니다. 공간 복잡도는 그중 한순간에 쥐고 있는 칸이 가장 많을 때를 셉니다. 크기 n 인 임시 목록을 만들었다 버리기를 열 번 되풀이해도 한꺼번에 쥐는 것은 n 칸입니다.

입력 공간과 보조 공간

코드가 쓰는 메모리는 두 몫으로 나뉩니다. 하나는 입력 자체를 담는 메모리입니다. 다른 하나는 코드가 일을 하려고 따로 더 쓰는 메모리입니다. 이것을 보조 공간이라고 부릅니다. 임시 변수, 복사본, 중간 결과를 담아 두는 목록이 보조 공간입니다.

입력은 코드가 무엇을 하든 이미 메모리에 있습니다. 그래서 방법끼리 비교할 때는 보조 공간만 세는 경우가 많습니다. 교재에 따라 입력까지 더한 값을 공간 복잡도라고 부르기도 합니다. 값을 볼 때는 어느 쪽을 센 것인지 먼저 확인합니다.

목록의 합계를 구하는 코드로 두 몫을 나눠 봅시다. 입력으로 n 칸짜리 목록을 받습니다. 합계를 담을 변수와 반복 변수로 두 칸을 더 씁니다. 입력까지 세면 n + 2 칸입니다. 보조 공간만 세면 2 칸입니다.

빅오 표기법으로 줄여 적기

센 칸 수는 줄여서 적습니다. 어떤 코드가 보조 공간으로 2n + 5 칸을 쓴다고 해 봅시다. 가장 빨리 자라는 항 하나만 남기고 그 앞의 상수도 떼면 n 만 남습니다. 이것을 O(n) 이라고 적고 「오 엔」이라고 읽습니다.

이렇게 줄여 적는 방식을 빅오 표기법이라고 부릅니다. O(n) 은 n 이 충분히 커지면 쓰는 칸 수가 n 에 어떤 상수를 곱한 값을 넘지 않는다는 뜻입니다. 칸 수가 늘어나는 꼴의 상한을 적는 셈입니다.

입력이 아무리 커져도 칸 수가 일정하면 O(1) 이라고 적습니다. 앞의 합계 코드가 보조 공간 O(1) 입니다. 이런 코드를 흔히 상수 공간만 쓴다고 말합니다.

재귀 호출이 쌓는 메모리

변수를 따로 만들지 않아도 메모리를 쓰는 때가 있습니다. 함수를 부를 때입니다. 프로그램은 함수 호출을 호출 스택이라는 메모리 공간에 차례로 쌓아 둡니다. 어느 함수가 어느 함수를 불러 놓고 기다리는지 기억하려는 것입니다.

호출 하나마다 호출 스택에 한 덩어리가 쌓입니다. 이 덩어리를 스택 프레임이라고 부릅니다. 그 호출의 지역 변수와 함수가 끝나면 돌아갈 곳이 여기 담깁니다. 함수가 끝나면 그 프레임을 치웁니다.

재귀 함수는 자기 자신을 다시 부르는 함수입니다. 앞 호출이 끝나기 전에 다음 호출의 프레임이 그 위에 쌓입니다. 재귀에서 한순간에 쥐는 칸이 가장 많을 때는 가장 깊이 들어갔을 때입니다. 그래서 재귀의 보조 공간은 호출 깊이를 따라갑니다.

아래 두 함수는 1부터 n 까지 더합니다. 하나는 재귀로, 하나는 반복문으로 짰습니다.

Python

def total_rec(n):   # 보조 공간 O(n)
    if n == 0:
        return 0
    return n + total_rec(n - 1)

def total_loop(n):  # 보조 공간 O(1)
    s = 0
    for i in range(1, n + 1):
        s += i
    return s

total_rec(3)        # 6
total_loop(3)       # 6

앞의 함수에서는 total_rec(3) 이 total_rec(2) 를 부릅니다. 그것이 다시 total_rec(1) 을 부르며 프레임을 위로 쌓습니다. 프레임마다 자기가 부른 호출의 답을 받아야 자기 덧셈을 끝낼 수 있습니다. 그래서 답이 올 때까지 기다리며 남아 있습니다.

뒤의 함수는 합계 s 와 반복 변수 i 두 칸만 씁니다. 답은 같고 쓰는 메모리의 꼴만 다릅니다.

아래 그림은 total_rec(3) 이 가장 깊이 들어간 순간의 호출 스택입니다. 맨 아래는 처음 부른 total_rec(3) 입니다. 맨 위는 마지막에 쌓인 total_rec(0) 입니다. n 이 백만이면 같은 순간에 프레임이 백만 개 넘게 쌓입니다.

flowchart TD
    subgraph S["가장 깊이 들어간 순간의 호출 스택"]
        F0["맨 위 · total_rec(0) · 0 을 돌려줌"]
        F1["total_rec(1) · 1 + ? 를 기다림"]
        F2["total_rec(2) · 2 + ? 를 기다림"]
        F3["맨 아래 · total_rec(3) · 3 + ? 를 기다림"]
    end
    F0 ~~~ F1
    F1 ~~~ F2
    F2 ~~~ F3

total_rec(0) 이 0 을 돌려주면 맨 위의 프레임부터 하나씩 치워집니다. 하나가 치워질 때마다 바로 아래 프레임이 답을 받아 덧셈을 끝냅니다. 마지막으로 total_rec(3) 이 6 을 돌려주면 스택이 빕니다.

호출 스택의 크기에는 한도가 있습니다. 재귀가 한도보다 깊어지면 스택 오버플로 오류가 나며 멈춥니다. 그래서 깊이가 입력에 비례하는 재귀는 반복문으로 바꿉니다.

스택은 나중에 넣은 것을 먼저 꺼내는 목록입니다. 반복문으로 바로 바꾸기 어려운 재귀는 이 목록을 코드에서 직접 만들어 씁니다. 함수를 다시 부르는 대신 할 일을 이 목록에 쌓으면 호출 스택의 한도를 피합니다. 보조 공간은 여전히 깊이만큼 듭니다.

범위를 반씩 줄이는 재귀는 사정이 다릅니다. 재귀로 짠 이진 탐색은 정렬된 목록에서 값을 찾을 때 한 번 부를 때마다 찾을 범위를 절반으로 줄입니다. n 이 백만이면 반씩 스무 번쯤 줄여서 범위가 하나로 좁혀집니다. 쌓이는 프레임도 스무 개쯤입니다.

n 을 반씩 몇 번 줄여야 1 이 되는지 나타내는 수를 log n 이라고 적습니다. 밑이 2 인 로그 함수입니다. 그래서 이 재귀의 보조 공간은 O(log n) 입니다.

그래프를 담는 두 방식

같은 데이터도 담는 방식에 따라 공간 복잡도가 갈립니다. 그래프는 노드와 노드를 잇는 간선으로 이루어진 구조입니다. 지하철 노선도라면 역이 노드이고 역 사이 선로가 간선입니다. 그래프를 메모리에 담는 흔한 방식이 둘 있습니다.

하나는 노드의 모든 쌍마다 칸을 하나씩 둔 표입니다. 두 노드가 이어져 있으면 그 칸에 표시합니다. 이것을 인접 행렬이라고 부릅니다. 노드가 n 개면 간선이 몇 개든 늘 n² 칸이 듭니다.

다른 하나는 노드마다 이어진 이웃만 목록으로 적어 두는 방식입니다. 이것을 인접 리스트라고 부릅니다. 노드 수에 간선 수를 더한 만큼만 칸이 듭니다.

노드가 백만 개이고 한 노드가 이웃 몇 개와만 이어진 그래프를 생각해 봅시다. 인접 행렬은 1조 칸이 듭니다. 인접 리스트는 몇백만 칸으로 끝납니다.

자주 만나는 꼴

실무에서 만나는 공간 복잡도는 대부분 몇 가지 꼴 안에 듭니다. 아래 표는 느리게 자라는 꼴부터 차례로 놓았습니다. 가운데 칸은 n 이 1,000 일 때 보조 공간이 대략 몇 칸인지 보입니다.

꼴	n = 1,000 일 때	이런 코드
O(1)	몇 칸	합계 구하기 · 반복문으로 짠 이진 탐색
O(log n)	약 10	재귀로 짠 이진 탐색
O(n)	1,000	목록 복사 · 깊이 n 까지 들어가는 재귀 · 읽은 값을 모두 담아 두는 목록
O(n²)	1,000,000	모든 값 쌍의 거리를 n × n 표에 적어 두기 · 노드 n 개인 그래프를 인접 행렬로 담기

반복문으로 짠 이진 탐색이 O(1) 인 까닭은 범위의 양 끝을 가리키는 수 두 개만 들고 다니기 때문입니다. 범위를 좁힐 때마다 그 두 수를 고쳐 쓸 뿐 새 칸을 만들지 않습니다.

O(n²) 은 대개 값의 쌍마다 칸을 하나씩 둘 때 나옵니다. 값이 n 개면 쌍은 n × n 개입니다. n 이 1,000 에서 10,000 으로 열 배가 되면 칸 수는 백 배가 됩니다.

같은 일을 하는 코드끼리도 꼴이 갈립니다. 병합 정렬은 목록을 둘로 나눠 정렬한 조각을 합칩니다. 합칠 때 결과를 담을 배열이 원래 크기만큼 더 들어서 보조 공간이 O(n) 입니다.

배열 안에서 값끼리 위치를 바꾸기만 하는 정렬은 몇 칸만 더 씁니다. 이런 정렬을 제자리 정렬이라고 부릅니다. 목록이 메모리를 거의 다 차지할 만큼 크면 여분의 배열을 둘 곳이 없습니다. 그럴 때 제자리 정렬을 고릅니다.

시간과 맞바꾸는 메모리

메모리를 더 쓰면 시간이 줄어드는 경우가 많습니다. 목록에 같은 값이 두 번 들어 있는지 확인하는 두 방법을 비교해 봅시다.

방법	시간	보조 공간
모든 쌍을 서로 비교하기	O(n²)	O(1)
본 값을 집합에 담아 두고 확인하기	평균 O(n)	O(n)

앞의 방법은 반복 변수 몇 칸만 씁니다. 대신 모든 쌍을 하나하나 비교하느라 시간이 n² 꼴로 늡니다.

뒤의 방법은 본 값을 집합에 담아 둡니다. 집합은 어떤 값이 들어 있는지 평균 한 번의 확인으로 알려 주는 모음입니다. 그래서 시간은 n 꼴로 줄어듭니다. 대신 집합이 최대 n 칸을 차지합니다.

이처럼 한쪽을 줄이려고 다른 쪽을 더 쓰는 선택을 시간과 공간 맞바꿈이라고 부릅니다. 메모리에 여유가 있으면 메모리를 더 써서 시간을 줄입니다. 여유가 없으면 시간을 더 들여 메모리를 아낍니다.

한 번 계산한 결과를 저장해 두고 같은 입력이 오면 다시 계산하지 않는 메모이제이션도 같은 선택입니다. 자주 쓰는 값을 가까운 메모리에 복사해 두는 캐싱도 메모리를 더 써서 시간을 줄입니다.

백엔드 코드에서 드러나는 대목

백엔드 개발자가 공간 복잡도를 가장 자주 만나는 때는 데이터를 한꺼번에 메모리에 올릴 때입니다. 파일의 모든 줄이나 데이터베이스 조회 결과 전체를 목록에 담으면 보조 공간이 O(n) 입니다. 개발 환경의 백 건에서는 티가 안 나다가 운영의 수천만 건에서 메모리가 바닥납니다.

아래 두 함수는 로그 파일에서 "error" 가 든 줄을 셉니다. 하는 일은 같고 공간 복잡도만 다릅니다.

Python

def count_all(path):     # O(n)
    with open(path) as f:
        lines = f.readlines()
    return sum("error" in x for x in lines)

def count_stream(path):  # O(1)
    with open(path) as f:
        return sum("error" in x for x in f)

앞의 함수는 파일의 모든 줄을 목록 lines 에 담은 뒤 셉니다. 파일이 커지면 목록도 같이 커집니다. 뒤의 함수는 파일 객체 f 에서 한 줄을 읽어 세고 버린 뒤 다음 줄을 읽습니다. 한 줄의 길이가 파일 크기와 상관없다고 보면 보조 공간은 O(1) 입니다.

이렇게 데이터를 조금씩 받아 가며 처리하는 방식을 스트리밍이라고 부릅니다. 데이터베이스에서 큰 결과를 커서로 조금씩 받거나 페이지네이션으로 나눠 받는 것도 같은 까닭에서 씁니다.

메모리가 바닥나면 두 가지 일이 생깁니다. 프로세스가 메모리 부족 오류를 내고 죽을 수 있습니다. 운영체제가 메모리 내용을 디스크로 내보내는 스와핑을 시작해 응답이 크게 늘어질 수도 있습니다.