공간 복잡도는 입력 증가에 따른 최대 저장 공간을 분석한다. 입력·출력·보조 공간, 복사와 참조, 재귀·제너레이터·캐시를 구분하고 LCS·배낭의 공간 압축과 실제 메모리 측정을 검증 예제로 설명한다.
개요: 실행 중 동시에 필요한 저장 공간
공간 복잡도(space complexity)는 입력 크기가 늘 때 알고리즘이 사용하는 저장 공간이 어떻게 증가하는지 분석하는 개념이다. 특정 컴퓨터에서 몇 MB를 썼는지 측정하는 것과 관련은 있지만 같은 수치는 아니다. 입력·출력·보조 자료·호출 스택 중 무엇을 포함하는지 먼저 정해야 한다.
예를 들어 목록을 합산할 때 모든 중간 합을 저장하면 원소 수에 비례한 공간이 필요하지만 최종 합 하나만 필요하다면 누적 변수만 유지할 수 있다. 두 방법은 같은 숫자를 반환하더라도 실행 중 보관해야 하는 상태가 다르다. 공간 개선은 필요 없는 상태의 수명을 줄이는 데서 시작한다.
이 문서는 보조 공간과 전체 공간, 최대 동시 사용량과 누적 할당량, 참조와 복사, 재귀·캐시·지연 평가를 구분한다. 동적 계획법의 두 행 압축과 0/1 배낭의 갱신 방향, 스트리밍과 실제 메모리 측정까지 예제로 연결한다.
실행 예제는 Python 3.9.6에서 검증했다. 원소 수를 세는 모델과 실제 바이트 측정을 구분하며, 플랫폼에 따라 달라지는 메모리 크기를 보편적인 숫자로 제시하지 않는다. 시간 복잡도와 마찬가지로 어떤 계산 모델을 가정했는지 함께 읽어야 한다.
입력·출력·보조 공간의 범위를 먼저 정한다
길이 n의 입력 목록이 이미 메모리에 있을 때 이를 합산하는 함수는 추가 상태를 거의 쓰지 않을 수 있다. 이때 보조 공간 O(1)이라고 말할 수 있지만 프로세스가 입력까지 포함해 O(1) 메모리만 사용한다는 뜻은 아니다. 입력 저장소 자체는 n개 원소를 차지한다.
출력 목록 n개를 새로 만드는 함수에서 출력 저장을 제외하면 보조 공간은 작을 수 있다. 반대로 전체 메모리를 비교할 때는 출력도 포함해야 한다. 같은 알고리즘을 두고 O(1)과 O(n)이라는 설명이 보이면 먼저 분석 범위가 같은지 확인한다.
아래 total은 누적 값만 유지하고 squares는 새 목록을 만든다. 결과 10과 [1,4,9,16]은 요구사항 자체가 다르므로 공간만 보고 어느 함수가 더 좋은지 비교할 수 없다. 모든 제곱 결과가 필요하다는 계약을 최종 합 하나로 바꿔서는 안 된다.
이 절의 상수 공간은 제한된 크기의 숫자를 일정한 슬롯으로 보는 모델이다. Python의 큰 정수 결과가 입력에 따라 커지는 경우에는 값의 비트 길이도 포함해야 한다. 변수 개수와 저장한 값의 크기는 같은 개념이 아니다.
예제 코드
def total(values):
result = 0
for value in values:
result += value
return result
values = [1, 2, 3, 4]
print(total(values))
print([value * value for value in values])실행 결과
10
[1, 4, 9, 16]최대 동시 사용량과 누적 할당량
한 번에 필요한 메모리를 판단할 때 중요한 것은 실행 전체에서 만든 모든 객체의 합이 아니라 어느 순간 동시에 살아 있는 객체의 최대량이다. 크기 n의 버퍼를 여러 번 만들었다가 버려도 동시에 하나만 유지하면 최대 공간은 O(n)일 수 있다. 누적 할당량과 할당 횟수는 별도의 비용이다.
반면 각 버퍼를 목록에 계속 보관하면 이전 버퍼가 살아 있으므로 최대 사용량도 합계만큼 늘어난다. 어디에 참조를 남겼는지가 객체의 수명을 결정한다. 임시 값이라는 이름을 붙였다고 자동으로 즉시 해제되는 것은 아니다.
아래 모델은 크기 10인 버퍼를 5번 처리할 때 누적 슬롯은 50이지만 한 개만 유지하면 최대 10,모두 보관하면 최대 50임을 계산한다. 실제 메모리 할당자를 측정한 결과가 아니라 공간 분석의 두 지표를 구분하는 숫자 예다.
변수에 새 버퍼를 대입하는 순간에는 새 값 생성이 끝나기 전까지 이전 값도 살아 있을 수 있다. 이런 일시적인 중첩은 점근 차수가 같아도 최대 바이트를 높일 수 있다. 큰 데이터 처리에서는 최종 결과 크기뿐 아니라 교체 순간의 피크도 중요하다.
예제 코드
buffer_size, rounds = 10, 5
cumulative = buffer_size * rounds
reuse_peak = buffer_size
retain_peak = buffer_size * rounds
print(cumulative, reuse_peak, retain_peak)실행 결과
50 10 50워드 모델과 비트 모델
알고리즘 설명에서는 인덱스나 작은 정수를 한 워드로 보고 상수 공간이라고 세는 경우가 많다. 그러나 이론적으로 n까지 표현하는 정수에는 대략 log₂n 비트가 필요하다. 워드 개수와 비트 개수는 서로 다른 분석 단위다.
Python int처럼 임의 정밀도 정수는 값이 커지면 저장 공간도 커진다. n!을 계산하는 코드가 변수 두 개만 쓴다고 전체 비트 공간까지 O(1)인 것은 아니다. 결과 자체의 크기가 증가하며 곱셈 중간 결과와 내부 연산 공간도 고려할 수 있다.
아래는 10!,20!,40!의 값 전체를 출력하지 않고 bit_length를 확인한다. 결과는 각각 22,62,160비트다. 객체 헤더와 내부 저장 단위까지 포함한 실제 Python 객체 바이트와는 다르지만 값이 차지하는 정보량이 상수가 아님을 보여준다.
문서에 “O(1) 추가 변수”와 “O(1) 비트”를 구분해 쓰면 이런 혼동을 피할 수 있다. 보통 실용 알고리즘 비교에서는 워드 모델이 유용하지만 암호학이나 큰 정수 계산처럼 값의 크기가 본질적인 분야에서는 비트 복잡도까지 검토한다.
예제 코드
from math import factorial
for n in [10, 20, 40]:
print(n, factorial(n).bit_length())실행 결과
10 22
20 62
40 160새 이름을 붙이는 것과 복사하기
Python에서 b=a는 같은 객체에 새 이름을 연결한다. 목록 전체를 복사하지 않는다. a.copy나 슬라이스는 바깥 목록을 새로 만들지만 안쪽 원소 객체는 공유하는 얕은 복사다. deepcopy는 객체 그래프를 더 깊게 복사하므로 비용과 의미가 달라진다.
아래 alias는 original과 같은 목록이고 shallow는 다른 바깥 목록이다. shallow[0]에 값을 추가하면 공유하는 안쪽 목록이 바뀌므로 original에도 보인다. 바깥 목록 하나를 새로 만들었다는 사실과 모든 내용이 독립되었다는 사실은 다르다.
공간을 셀 때 여러 참조가 같은 객체를 가리키면 객체 내용을 참조 수만큼 중복해서 더하지 않는다. 반대로 컨테이너 슬롯은 각각의 참조를 저장하므로 슬롯 비용 자체는 별도로 존재한다. 공유 객체 그래프의 크기를 재려면 방문한 객체를 식별하는 등의 중복 계산 방지가 필요하다.
깊은 복사도 모든 자원을 의미 있게 복제하는 만능 기능은 아니다. 파일·잠금·외부 연결과 순환 참조를 어떻게 처리하는지 API의 계약을 확인한다. 메모리를 줄이려고 공유를 늘리면 변경의 전파와 소유권이라는 다른 문제를 함께 다루어야 한다.
예제 코드
original = [[1], [2]]
alias = original
shallow = original.copy()
print(alias is original, shallow is original)
print(shallow[0] is original[0])
shallow[0].append(9)
print(original)실행 결과
True False
True
[[1, 9], [2]]슬라이스와 숨겨진 중간 결과
목록 슬라이스 values[a:b]는 선택한 원소의 참조를 담는 새 목록을 만든다. 길이 k인 슬라이스라면 k개의 슬롯이 필요하다. 코드가 한 줄이거나 함수 인수로 즉시 넘긴다고 그 공간이 없어지는 것은 아니다.
반복적으로 점점 짧은 슬라이스를 재귀 호출에 넘기면 각 호출이 이전 목록을 유지하는 동안 새 목록이 추가될 수 있다. 인덱스 범위만 전달하는 구현과 같은 공간 분석을 적용해서는 안 된다. 호출 스택뿐 아니라 호출마다 만든 자료의 수명을 함께 본다.
아래 prefix_sizes는 길이 1부터 5까지의 접두 목록을 모두 보관한다. 바깥 목록에 5개 참조가 있고 안쪽 목록의 슬롯은 합계 15개다. 원소 객체 자체는 공유될 수 있지만 목록 저장 공간은 합산된다.
중간 결과를 없애려면 인덱스·이터레이터·뷰를 사용할 수 있지만 반환값의 수명과 원본 변경 의미가 달라질 수 있다. 복사를 줄이는 변경이 기존 호출자가 기대한 독립적인 결과를 공유 뷰로 바꾸지 않는지 확인한다.
예제 코드
values = [10, 20, 30, 40, 50]
prefixes = [values[:end] for end in range(1, 6)]
print([len(part) for part in prefixes])
print(sum(len(part) for part in prefixes))실행 결과
[1, 2, 3, 4, 5]
15작은 뷰가 큰 원본을 붙잡는 경우
뷰는 원본 데이터를 복사하지 않고 일부 범위를 바라보므로 생성 비용을 줄일 수 있다. 하지만 작은 뷰가 살아 있는 동안 큰 원본 저장소도 유지될 수 있다. 보이는 길이가 작다고 소유하거나 붙잡는 메모리도 작다는 보장은 없다.
아래 bytearray 10,000바이트의 마지막 10바이트를 memoryview로 본다. 뷰의 길이는 10이지만 view.obj는 원래 버퍼다. bytes(view)로 복사하면 작은 독립 바이트 객체를 만들 수 있으며 그 대신 복사 비용을 지불한다.
어떤 상황에서는 이 작은 복사가 장기적으로 큰 메모리를 해제하는 데 도움이 된다. 반대로 원본을 어차피 계속 사용한다면 복사는 중복 저장만 늘릴 수 있다. 객체 생존 기간과 소유 관계를 기준으로 판단해야 한다.
memoryview가 잡고 있는 버퍼의 크기 변경 등은 해당 타입과 뷰의 제약을 따라야 한다. 모든 슬라이스가 뷰인 것도 아니며 Python list 슬라이스는 다른 의미다. 언어·라이브러리별 API를 확인하지 않고 “슬라이스는 O(1)”이라고 일반화하지 않는다.
예제 코드
buffer = bytearray(10000)
view = memoryview(buffer)[-10:]
small_copy = bytes(view)
print(len(view), view.obj is buffer)
print(len(small_copy), isinstance(small_copy, bytes))
view.release()실행 결과
10 True
10 True재귀 공간은 총 호출 수가 아니라 깊이부터 본다
재귀 함수의 공간은 동시에 활성화된 호출 프레임과 각 프레임이 유지하는 자료를 분석한다. 전체 실행에서 함수가 1,000번 호출되었어도 대부분 순서대로 끝나고 최대 깊이가 10이면 호출 프레임 공간은 깊이 10에 대응한다.
문제를 둘로 나누어 두 하위 호출을 순차적으로 실행하는 재귀는 전체 호출 수가 많아도 깊이가 로그일 수 있다. 하지만 분할한 배열을 복사해 각 호출이 보관하면 자료 공간이 추가된다. “분할 정복이므로 O(log n) 공간”이라는 단정에는 숨은 가정이 있다.
아래 재귀는 숫자 크기를 절반으로 줄이는 깊이만 계산하며 배열을 만들지 않는다. n=8과 16의 활성 호출 수는 기저 호출을 포함해 4와 5다. 정확한 깊이와 점근적인 O(log n)을 함께 확인하는 예다.
꼬리 재귀 형태라고 모든 언어가 프레임을 제거하는 것도 아니다. Python에서 일반적인 재귀를 반복문으로 바꾸면 호출 깊이를 줄일 수 있지만 알고리즘이 보존해야 하는 상태까지 자동으로 없어지지는 않는다. 명시적 스택을 쓰면 그 저장 공간을 별도로 센다.
예제 코드
def depth(n):
if n <= 1:
return 1
return 1 + depth(n // 2)
print(depth(8), depth(16))실행 결과
4 5탐색의 공간: 깊이와 너비는 다르다
트리 DFS는 현재 경로와 다음에 처리할 상태를 보관하고 BFS는 현재·다음 층의 대기 정점을 보관한다. 가느다란 긴 트리와 얕지만 폭이 넓은 트리에서는 필요한 상태량이 다르게 나타난다. 입력 크기 n 하나만으로 실제 피크의 형태를 모두 설명할 수는 없다.
별 모양 트리에서 중심의 자식이 n-1개이면 BFS 큐에 많은 자식이 한꺼번에 들어갈 수 있다. 반면 재귀 DFS의 활성 경로 깊이는 작을 수 있다. 그러나 정점을 한꺼번에 스택에 넣는 단순 반복 DFS는 별 모양에서도 많은 항목을 보관할 수 있으므로 “DFS 공간은 항상 깊이”라고 말하면 부정확하다.
일반 그래프에서는 순환과 중복 방문을 막는 visited 집합이 필요할 수 있다. 탐색 스택이 작아도 방문 표시가 O(V)면 전체 보조 공간도 그 영향을 받는다. 결과 경로·거리 사전·입력 그래프의 저장 공간도 분석 범위에 맞춰 더한다.
메모리를 줄이려고 visited를 제거하면 같은 정점을 반복하거나 순환에서 끝나지 않을 수 있다. 정확성을 유지하는 제한 조건이나 다른 탐색 방법이 있는지 확인해야 한다. 저장량 감소를 위해 재계산을 늘리는 선택은 시간과 함께 평가한다.
지연 평가는 결과를 언제 보관하는지 바꾼다
제너레이터는 결과를 필요할 때 하나씩 생성하여 모든 결과를 한꺼번에 목록으로 저장하지 않을 수 있다. 예를 들어 제곱의 합만 필요하다면 제곱 목록을 만든 뒤 합치는 대신 값을 생성하면서 합산할 수 있다. 요구하는 최종 결과는 같고 중간 저장량이 줄어든다.
아래 두 계산은 모두 30을 반환한다. 첫 번째는 네 제곱값을 목록에 보관하고 두 번째는 생성한 값을 차례로 합산한다. 실제 정수 객체의 수명과 내장 함수의 내부 상태를 제외한 알고리즘 모델에서 중간 목록 O(n)을 없앤 것이다.
제너레이터를 만든 시점에는 본문 계산이 아직 실행되지 않았을 수 있다. 생성 객체만 측정하고 소비 비용을 빼면 시간과 공간을 잘못 비교할 수 있다. 모든 결과를 list(generator)로 모으면 다시 출력 크기만큼의 저장 공간이 생긴다.
제너레이터가 원본 목록이나 큰 지역 버퍼를 참조하면 그 자료는 계속 살아 있을 수 있다. yield가 있다는 문법만으로 메모리가 상수라고 판단하지 않는다. 프레임 안에 무엇을 유지하고 소비자가 결과를 어떻게 보관하는지까지 살펴야 한다.
예제 코드
values = range(1, 5)
materialized = [value * value for value in values]
streamed = (value * value for value in values)
print(sum(materialized), sum(streamed))
print(list(streamed))실행 결과
30 30
[]이터레이터를 복제할 때 숨은 버퍼
하나의 입력 스트림을 여러 소비자가 독립적으로 읽으려면 이미 한 소비자가 읽었지만 다른 소비자가 아직 읽지 않은 값을 보관해야 할 수 있다. itertools.tee는 이런 지연 복제를 제공하지만 소비자 진행 속도 차이에 따라 내부 저장이 커질 수 있다.
아래 fast가 다섯 값을 먼저 읽어도 slow는 처음 값부터 읽을 수 있다. 원래 입력을 되감은 것이 아니라 다른 소비자에게 필요한 값을 유지하는 방식이 개입한다. 구체적인 내부 블록 크기를 가정하지 않아도 소비자 간 지연이 공간 요구와 연결된다는 점은 이해할 수 있다.
한 소비자가 입력 전체를 읽고 다른 소비자가 전혀 읽지 않으면 지연 평가를 사용했어도 많은 값이 보관될 수 있다. 소비자 간 속도 차이를 제한하거나 서로 독립적으로 다시 읽을 수 있는 입력을 활용하는 방법을 비교한다.
무한 스트림을 list로 만들거나 한 소비자가 영원히 뒤처지는 구조는 유한 메모리에서 완료할 수 없다. 스트리밍이라는 이름보다 버퍼가 어느 조건에서 늘고 줄어드는지가 실제 공간을 결정한다.
예제 코드
from itertools import tee
fast, slow = tee(iter(range(6)))
print([next(fast) for _ in range(5)])
print(next(slow), next(slow))
print(list(fast))실행 결과
[0, 1, 2, 3, 4]
0 1
[5]메모이제이션: 시간과 공간을 교환한다
이미 계산한 상태의 결과를 캐시에 보관하면 반복 계산을 줄일 수 있다. 하지만 상태 수가 늘어날수록 캐시 공간도 증가한다. 피보나치처럼 같은 하위 문제를 많이 방문하는 경우 시간 감소가 크지만 모든 입력이 서로 다르면 캐시가 적중하지 않고 저장만 늘 수 있다.
캐시의 키도 메모리를 사용한다. 긴 문자열이나 큰 튜플을 키로 유지하면 결과보다 키의 공간이 더 클 수 있다. 함수 결과에 큰 객체 그래프가 연결되어 있으면 캐시 엔트리 수만으로 전체 바이트를 예측하기 어렵다.
아래 lru_cache(maxsize=3)는 최대 세 입력의 결과를 유지한다. 네 개의 서로 다른 값을 계산한 뒤 currsize는 3이다. 다시 필요한 값이 제거되었다면 재계산이 일어나므로 제한된 캐시는 무제한 캐시와 같은 시간 보장을 주지 않는다.
캐시 공간을 분석할 때 최대 항목 수, 항목 크기, 만료·제거 정책과 객체 생존 기간을 함께 적는다. cache_clear 같은 명시적 정리를 사용할 때도 이후 재계산 비용과 동시 호출의 의미를 검토한다.
예제 코드
from functools import lru_cache
@lru_cache(maxsize=3)
def square(value):
return value * value
for value in range(4):
square(value)
print(square.cache_info().currsize)
square.cache_clear()
print(square.cache_info().currsize)실행 결과
3
0동적 계획법의 전체 표: 의존 관계가 출발점
최장 공통 부분 수열의 길이를 구하는 LCS는 두 문자열의 접두 구간 조합을 상태로 만들 수 있다. 길이가 n,m이면 (n+1)×(m+1)개의 칸을 사용한다. 각 칸은 위·왼쪽·왼쪽 위의 값을 참조하므로 표를 채우는 순서를 정할 수 있다.
아래 lcs_table은 두 문자가 같으면 왼쪽 위에 1을 더하고 다르면 위와 왼쪽의 큰 값을 고른다. ABCBDAB과 BDCABA의 LCS 길이는 4다. 어떤 부분 수열을 반환하는 함수가 아니라 길이 하나를 반환하는 함수라는 점이 중요하다.
시간은 O(nm), 보조 표 공간은 O(nm)이다. Python의 각 정수 객체 크기까지 정확한 바이트로 계산한 것이 아니라 칸 수 모델이다. n과 m이 서로 다른 입력 변수임을 유지하면 어느 쪽이 작은지 활용한 공간 개선을 설명하기 쉽다.
전체 표를 저장하면 이후 경로를 따라 실제 부분 수열을 복원하는 데 활용할 수 있다. 길이만 구할 때는 모든 행을 끝까지 유지할 필요가 없으며, 이 요구사항 차이가 다음 절의 공간 압축 근거가 된다.
예제 코드
def lcs_table(a, b):
rows, cols = len(a), len(b)
table = [[0] * (cols + 1) for _ in range(rows + 1)]
for i in range(1, rows + 1):
for j in range(1, cols + 1):
if a[i - 1] == b[j - 1]:
table[i][j] = table[i - 1][j - 1] + 1
else:
table[i][j] = max(table[i - 1][j], table[i][j - 1])
return table[rows][cols]
print(lcs_table('ABCBDAB', 'BDCABA'))
print(lcs_table('', 'ABC'))실행 결과
4
0두 행으로 줄이기: 더 이상 읽지 않는 상태 버리기
LCS의 현재 행을 계산할 때 필요한 것은 이전 행과 현재 행의 왼쪽 부분이다. 그보다 오래된 행은 다시 참조하지 않으므로 버릴 수 있다. 아래 lcs_rows는 이전 행과 새 행만 유지하여 표 공간을 O(min(n,m))으로 줄인다.
짧은 문자열을 열 방향으로 두기 위해 필요하면 두 문자열의 역할을 바꾼다. LCS 길이는 두 입력을 바꾸어도 같으므로 의미를 보존한다. 문자열을 통째로 복사하는 것이 아니라 Python 이름을 교환하므로 교환 자체에 입력 크기만큼의 새 저장을 요구하지 않는다.
각 바깥 반복마다 새 행을 만들기 때문에 전체 실행의 누적 할당량은 여전히 O(nm)개의 칸에 대응할 수 있다. 그러나 동시에 유지하는 행은 상수 개이므로 최대 보조 공간은 선형이다. 최대 동시 사용량과 누적 할당량을 구분해야 이 개선을 정확히 설명할 수 있다.
출력은 앞의 전체 표와 같은 4와 0이다. 실제 부분 수열 복원을 요구한다면 두 행만 남기는 구현에서 추가 설계가 필요하다. 더 많은 재계산이나 분할 정복 복원 등 시간·구현 복잡성의 교환을 고려해야 하며 길이 함수의 보장을 그대로 확장하지 않는다.
예제 코드
def lcs_rows(a, b):
if len(a) < len(b):
a, b = b, a
previous = [0] * (len(b) + 1)
for left in a:
current = [0] * (len(b) + 1)
for j, right in enumerate(b, 1):
if left == right:
current[j] = previous[j - 1] + 1
else:
current[j] = max(previous[j], current[j - 1])
previous = current
return previous[-1]
print(lcs_rows('ABCBDAB', 'BDCABA'))
print(lcs_rows('', 'ABC'))실행 결과
4
0한 행 압축에서 갱신 방향이 의미를 바꾼다
0/1 배낭 문제는 각 물건을 최대 한 번 선택한다. 한 차원 표로 줄일 때 용량을 큰 값에서 작은 값으로 갱신하면 현재 물건을 아직 반영하지 않은 작은 용량 상태를 읽는다. 반대로 작은 값부터 갱신하면 방금 갱신한 값을 다시 사용하여 같은 물건을 반복 선택할 수 있다.
아래 물건 하나의 무게는 2,가치는 3이고 용량은 4다. 0/1 조건에서 답은 3이다. 잘못된 오름차순 갱신은 용량 2의 새 값 3을 용량 4에서 다시 읽어 6을 만든다. 메모리를 줄이는 변화가 문제의 의미까지 바꾼 사례다.
knapsack 예제는 값과 무게 목록 길이가 같고 무게가 양의 정수, 용량이 음이 아닌 정수라는 전제를 둔다. 반환값은 최대 가치 하나이며 선택한 물건 목록은 복원하지 않는다. 시간 O(물건 수×용량), 공간 O(용량)은 용량의 수치에 대한 분석이다.
용량을 이진수로 입력받으면 입력 비트 길이는 log 용량에 비례하므로 이 표 크기를 입력 길이에 대한 다항 공간이라고 자동으로 부를 수는 없다. 수치 크기와 표현 길이의 차이는 시간과 공간 모두에 적용된다.
예제 코드
def knapsack(values, weights, capacity):
best = [0] * (capacity + 1)
for value, weight in zip(values, weights):
for limit in range(capacity, weight - 1, -1):
best[limit] = max(best[limit], best[limit - weight] + value)
return best[capacity]
print(knapsack([3], [2], 4))
wrong = [0] * 5
for limit in range(2, 5):
wrong[limit] = max(wrong[limit], wrong[limit - 2] + 3)
print(wrong[4])실행 결과
3
6제자리 알고리즘과 숨은 호출 스택
제자리 처리는 입력 저장소를 직접 바꾸어 별도의 큰 결과 배열을 피하는 방식이다. 하지만 제자리라는 표현이 언제나 보조 공간을 정확히 0으로 만든다는 뜻은 아니다. 몇 개의 임시 변수나 재귀 호출 스택을 사용할 수 있으므로 사용한 정의를 밝힌다.
아래 reverse_in_place는 양 끝을 교환하고 가운데로 이동한다. 입력 목록 객체를 유지하면서 [1,2,3,4,5]를 [5,4,3,2,1]로 바꾼다. 인덱스와 임시 교환 상태만 쓰는 모델에서 보조 공간은 O(1)이다.
원본 순서를 다른 코드가 계속 필요로 한다면 이 변경은 적절하지 않을 수 있다. 복사본을 만든 뒤 제자리 정렬·뒤집기를 실행하면 전체 절차는 복사 공간 O(n)을 사용한다. 마지막 함수 하나만 보고 전체 파이프라인의 공간을 상수라고 보고하지 않는다.
재귀적인 제자리 알고리즘은 호출 스택을 별도로 분석한다. 배열 분할 자체가 별도 버퍼를 쓰지 않아도 깊이에 따라 프레임 공간이 생긴다. 라이브러리가 제공하는 정렬의 실제 보조 공간 보장은 문서나 구현 조건을 확인해야 한다.
예제 코드
def reverse_in_place(values):
left, right = 0, len(values) - 1
while left < right:
values[left], values[right] = values[right], values[left]
left += 1
right -= 1
values = [1, 2, 3, 4, 5]
alias = values
reverse_in_place(values)
print(values, alias is values)실행 결과
[5, 4, 3, 2, 1] True행렬 생성의 별칭 오류
행렬을 만들 때 같은 행 객체를 여러 번 참조하면 필요한 공간은 줄어든 것처럼 보이지만 독립적인 행이라는 의미가 깨진다. Python의 [[0]*3]*2는 행 두 개를 따로 만드는 것이 아니라 같은 행 참조를 두 번 저장한다.
아래 bad[0][0]만 바꾸었는데 두 행 모두 첫 값이 9가 된다. good은 각 반복에서 새 행을 만들므로 첫 행만 바뀐다. 메모리가 적게 쓰인 결과가 올바른 자료 표현인지 먼저 확인해야 한다.
공유가 의도된 경우에는 같은 객체를 참조하는 것이 유용하다. 하지만 동적 계획법의 서로 다른 행을 같은 객체로 두면 갱신 순서와 의존 관계가 무너지며 잘못된 답을 만들 수 있다. 공간 압축은 명시적으로 설계한 상태 재사용이어야 한다.
이 예제는 객체 수와 참조 수를 구별하는 테스트이기도 하다. 값만 한 번 출력해서 같다고 확인하기보다 한 부분을 변경했을 때 다른 부분이 독립적인지 검사하면 구조적 오류를 드러낼 수 있다.
예제 코드
bad = [[0] * 3] * 2
bad[0][0] = 9
print(bad)
good = [[0] * 3 for _ in range(2)]
good[0][0] = 9
print(good)
print(bad[0] is bad[1], good[0] is good[1])실행 결과
[[9, 0, 0], [9, 0, 0]]
[[9, 0, 0], [0, 0, 0]]
True False출력 크기의 하한과 지연 생성
n개 원소를 독립적으로 고르는 모든 부분집합은 2^n개다. 각 결과를 실제 목록으로 보관하려면 출력 자체가 큰 공간을 요구한다. 보조 자료를 아무리 줄여도 모든 결과를 한꺼번에 저장한다는 계약의 하한은 피할 수 없다.
결과를 하나씩 내보내면 동시에 보관하는 출력량을 줄일 수 있다. 그러나 소비자가 모든 결과를 다시 목록에 모으면 전체 시스템의 저장량은 여전히 크다. 생산자 함수만 분석하고 소비자의 결과 축적을 빼면 실제 메모리 요구를 과소평가한다.
길이 n의 모든 이진 문자열을 저장하면 문자 수 합계는 n·2^n이다. 아래 n=4,8,12의 결과 수와 문자 수를 계산한다. 실제 객체 헤더나 인코딩 바이트는 포함하지 않은 정보량 모델이며 입력이 조금 늘어도 출력이 급증함을 보여준다.
문제에 따라 모든 결과 대신 개수·최댓값·대표 결과 하나만 필요한지 확인하면 큰 개선이 가능하다. 다만 사용자가 실제로 모든 결과를 요구하는데 요약만 반환하면 같은 문제를 푼 것이 아니다. 공간 최적화와 요구사항 변경을 분명히 구별한다.
예제 코드
for n in [4, 8, 12]:
count = 2 ** n
print(n, count, n * count)실행 결과
4 16 64
8 256 2048
12 4096 49152비트 집합과 표현 방식의 영향
참·거짓 상태 n개를 각각 일반 객체로 저장하는 방식과 비트 n개로 압축하는 방식은 실제 공간 상수가 크게 다를 수 있다. 둘 다 n에 선형이라고 표현해도 바이트 수준의 비용은 같지 않다. 표현을 바꾸면 지원하는 연산과 변환 비용도 달라진다.
아래는 값 1,3,5의 존재를 정수 마스크에 기록한다. mask는 42이고 비트 검사를 통해 3은 있으며 4는 없음을 알 수 있다. 이 작은 예제는 집합의 원소가 제한된 음이 아닌 정수라는 전제를 사용한다.
최댓값 U가 매우 크고 실제 원소는 적으면 U에 비례한 비트 공간이 오히려 비효율적일 수 있다. 희소 집합을 해시 구조로 저장하는 방법과 밀집 비트 집합을 비교할 때는 원소 수 n과 값의 범위 U를 분리해야 한다.
Python 큰 정수의 비트 연산이 무조건 O(1)인 것은 아니다. 마스크의 비트 길이가 커지면 연산과 저장 비용도 증가한다. 한 변수에 담았다는 이유로 상수 공간·상수 시간으로 분류하지 않는다.
예제 코드
mask = 0
for value in [1, 3, 5]:
mask |= 1 << value
print(mask)
print(bool(mask & (1 << 3)), bool(mask & (1 << 4)))
print(bin(mask).count('1'))실행 결과
42
True False
3스트리밍과 청크 처리의 경계
파일 전체를 읽어 처리하는 대신 일정 크기의 청크를 읽으면 입력 크기에 비례한 메모리를 피할 수 있다. 하지만 청크 경계에서 레코드가 잘리는 경우를 처리할 상태가 필요하며 한 레코드 자체가 매우 크면 그 버퍼가 커질 수 있다.
줄 단위 반복도 항상 엄격한 상수 바이트를 보장하지 않는다. 한 줄의 최대 길이에 제한이 없다면 읽는 한 줄의 크기가 입력 전체만큼 클 수 있다. 고정 청크 처리는 입력 버퍼를 제한하지만 구문 분석과 결과 저장이 추가로 커질 수 있다.
아래는 메모리 BytesIO를 사용해 청크 크기 3으로 바이트 합을 구한다. 실제 파일 시스템을 읽는 성능 실험이 아니라 청크 처리의 상태량을 보여주는 예다. 원본 8바이트는 이미 메모리에 있으므로 이 예제 프로그램 전체가 3바이트만 사용한다고 말할 수 없다.
스트리밍 알고리즘을 평가할 때는 입력 제공자, 중간 버퍼, 미완료 레코드와 출력 소비자까지 포함한 경계를 정한다. 파이프라인 각 단계가 결과를 계속 저장하면 한 단계의 작은 버퍼만으로 전체 공간을 설명할 수 없다.
예제 코드
from io import BytesIO
source = BytesIO(b'abcdefgh')
checksum = 0
largest_chunk = 0
while True:
chunk = source.read(3)
if not chunk:
break
checksum += sum(chunk)
largest_chunk = max(largest_chunk, len(chunk))
print(checksum, largest_chunk)실행 결과
804 3병렬 작업은 버퍼를 여러 벌 유지할 수 있다
작업 하나가 B 크기의 버퍼를 사용하고 W개가 동시에 실행되면 작업 버퍼만 W·B가 필요할 수 있다. 공유 입력을 읽는지 각 작업이 복사본을 만드는지에 따라 입력 공간도 달라진다. 병렬화로 시간이 줄어도 메모리 피크가 증가할 수 있다.
대기 큐가 Q개 항목을 보관하고 항목당 평균 크기가 S라면 대기 자료 공간도 대략 Q·S로 생각할 수 있다. 그러나 항목이 큰 공유 객체를 참조하는 경우 중복 합산을 피해야 하고, 처리 중인 항목은 큐 길이에서 빠져도 계속 메모리에 남는다.
아래 간단한 모델은 작업 버퍼 4×8과 대기 항목 10×2를 합해 52단위를 계산한다. 런타임·스레드 스택·입력 공유와 객체 헤더는 제외한 예산 모델이다. 측정 결과가 아니므로 실제 MB 수치로 해석하지 않는다.
메모리 상한을 지키려면 대기 큐 용량과 실행 동시 수를 함께 제한한다. 한쪽만 제한하면 다른 쪽이 과도하게 커질 수 있다. 병렬 처리를 조정할 때 처리량뿐 아니라 피크 메모리와 실패 시 재시도 버퍼도 관찰한다.
예제 코드
workers, buffer_units = 4, 8
queued, item_units = 10, 2
print(workers * buffer_units + queued * item_units)실행 결과
52sys.getsizeof는 객체 그래프 전체가 아니다
Python sys.getsizeof는 객체 자체의 크기를 반환하며 일반적으로 그 객체가 참조하는 모든 객체의 크기를 재귀적으로 더하지 않는다. 목록의 크기를 보고 그 안의 긴 문자열이나 하위 목록까지 포함했다고 생각하면 실제 보유 공간을 과소평가할 수 있다.
반대로 같은 큰 객체를 여러 슬롯에서 참조할 때 매번 그 객체 크기를 더하면 중복 계산한다. 정확한 보유 공간 분석은 공유·순환·외부 자원·런타임 구현을 고려해야 하며 간단한 재귀 합산 함수 하나로 모든 타입을 정확히 처리하기 어렵다.
아래 두 목록은 같은 내용의 큰 bytearray 하나를 각각 한 번과 세 번 참조한다. 유일한 원소 객체 수는 모두 1이다. 슬롯 수는 다르지만 실제 버퍼를 세 벌 만든 것은 아니다. 이 예제는 특정 플랫폼의 바이트 수를 출력하지 않고 소유 관계를 확인한다.
측정값을 공유할 때 Python 구현과 버전, 플랫폼, 입력 구성과 포함 범위를 기록한다. 객체의 직접 크기, 참조로 유지되는 크기, 프로세스 전체 메모리는 각각 다른 질문에 대한 답이다.
예제 코드
payload = bytearray(1000)
one = [payload]
three = [payload, payload, payload]
print(len(one), len(three))
print(len({id(x) for x in one}), len({id(x) for x in three}))실행 결과
1 3
1 1tracemalloc로 현재와 피크를 구분하기
tracemalloc은 Python이 추적하는 메모리 블록의 할당 정보를 조사하는 도구다. 현재 추적 중인 크기와 추적 구간의 피크를 구분할 수 있고 스냅샷 차이로 어느 코드가 메모리를 늘렸는지 살펴볼 수 있다. 추적 시작 전에 이미 할당된 자료와 모든 네이티브 메모리를 자동으로 포함하는 것은 아니다.
아래는 추적을 시작하고 100,000바이트 bytearray를 만든 뒤 현재와 피크를 읽는다. 객체를 삭제한 뒤의 현재 값은 줄어드는지 확인하고, 피크가 현재보다 작지 않다는 관계를 출력한다. 환경마다 달라지는 원시 바이트를 고정된 정답으로 적지 않는다.
추적 도구 자체에도 비용이 있으므로 성능 측정과 메모리 진단의 목적을 구분한다. 비교하려는 두 함수를 동일한 입력과 워밍업·추적 범위에서 실행하고, 결과가 살아 있는 시점인지 반환 후 해제한 시점인지 일관되게 정한다.
프로세스의 운영체제 메모리 지표는 할당자 캐시나 확장 모듈, 공유 메모리 등 다른 요인을 포함할 수 있다. tracemalloc 값과 프로세스 지표가 다르다고 어느 한쪽이 틀렸다고 단정하지 말고 측정 범위의 차이를 조사한다.
예제 코드
import tracemalloc
tracemalloc.start()
buffer = bytearray(100000)
current, peak = tracemalloc.get_traced_memory()
del buffer
remaining, later_peak = tracemalloc.get_traced_memory()
tracemalloc.stop()
print(current > 0, peak >= current)
print(remaining < current, later_peak >= peak)실행 결과
True True
True True살아 있는 참조와 메모리 누수 진단
사용을 끝낸 데이터를 전역 목록, 캐시, 클로저나 콜백이 참조하면 그 객체가 계속 살아 있을 수 있다. 가비지 컬렉션이 존재해도 프로그램이 여전히 도달 가능한 객체를 보관하면 의도한 시점에 회수되지 않는다. 논리적인 수명과 참조 그래프를 함께 살펴야 한다.
메모리가 한 번 증가한 뒤 유지된다는 관찰만으로 누수라고 확정할 수는 없다. 재사용을 위해 용량을 보유하거나 할당자가 공간을 캐시할 수 있다. 같은 작업을 반복할 때 살아 있는 객체와 보유 자료가 계속 누적되는지, 안정된 상한에 도달하는지 구분한다.
캐시를 비우거나 del로 이름을 제거해도 다른 참조가 남아 있으면 객체는 유지된다. 객체가 해제되더라도 프로세스의 메모리가 운영체제에 즉시 반환되는지는 별도 문제다. 원인을 찾으려면 객체의 생성 위치와 보관 경로를 추적한다.
공간 복잡도는 입력 크기 증가에 따른 상한 분석이고 누수 진단은 반복 실행과 수명 관리의 문제다. 둘은 연결되지만 같은 결론은 아니다. 입력 크기가 고정되어 있어도 요청마다 자료를 계속 보관하면 장기 운영에서 사용량이 증가할 수 있다.
공간 압축의 정확성을 완전 열거로 확인하기
LCS의 전체 표와 두 행 버전이 같은 답을 내는지 작은 입력 전체에서 비교할 수 있다. a,b 두 글자로 길이 0부터 4까지 만들 수 있는 문자열은 31개이고 두 입력 조합은 961개다. 각 조합에서 가능한 부분 수열을 직접 열거한 길이도 기준으로 사용한다.
전체 표와 두 행 버전이 같은 점화식을 공유하므로 둘만 비교하면 공통 오류를 놓칠 수 있다. 부분 수열 집합의 교집합을 구하는 느리지만 다른 방식의 기준을 추가하면 독립성을 높일 수 있다. 이 기준은 작은 입력에서만 쓰는 검증 도구다.
앞의 lcs_table과 lcs_rows 정의 뒤에 실행하면 두 구현 각각 961개,총 1,922개 결과 비교가 통과한다. 빈 문자열과 반복 문자도 포함된다. 더 큰 입력의 모든 경우에 대한 증명은 상태 의존 관계로 별도 설명하며 테스트로 대체하지 않는다.
예제 코드
from itertools import product
words = [''.join(chars) for length in range(5)
for chars in product('ab', repeat=length)]
def subsequences(text):
return {''.join(text[i] for i in range(len(text)) if mask & (1 << i))
for mask in range(1 << len(text))}
checks = 0
for a in words:
for b in words:
expected = max(map(len, subsequences(a) & subsequences(b)))
assert lcs_table(a, b) == expected
assert lcs_rows(a, b) == expected
checks += 2
print(checks)실행 결과
1922배낭 압축을 부분집합 기준으로 검사하기
0/1 배낭의 갱신 방향 오류는 물건을 여러 번 사용할 수 있는 입력에서 드러난다. 아래는 물건 수 0부터 3,무게 1부터 3,가치 1부터 2의 모든 조합과 용량 0부터 6을 검사한다. 각 입력의 모든 부분집합을 열거해 가능한 최대 가치를 구한다.
총 1,813개 경우를 한 행 knapsack 결과와 비교한다. 무게가 용량보다 큰 물건,같은 무게와 가치가 반복되는 물건,빈 입력과 용량 0이 포함된다. 물건 순서를 바꾸더라도 최대 가치가 유지되어야 하는 요구도 다양한 조합에 반영된다.
값·무게 목록 길이가 같고 무게가 양수라는 전제를 검사 입력이 따른다. API를 외부에 공개한다면 전제 위반을 어떻게 처리할지 별도의 검증을 추가한다. 공간 최적화의 성공은 메모리 감소뿐 아니라 같은 문제의 같은 답을 보존하는 것으로 확인한다.
예제 코드
from itertools import product
checks = 0
items = list(product(range(1, 4), range(1, 3)))
for length in range(4):
for choice in product(items, repeat=length):
weights = [item[0] for item in choice]
values = [item[1] for item in choice]
for capacity in range(7):
expected = 0
for mask in range(1 << length):
weight = sum(weights[i] for i in range(length) if mask & (1 << i))
value = sum(values[i] for i in range(length) if mask & (1 << i))
if weight <= capacity:
expected = max(expected, value)
assert knapsack(values, weights, capacity) == expected
checks += 1
print(checks)실행 결과
1813분석 결과를 문서에 남기는 순서
먼저 입력 크기와 분석 단위를 정한다. n이 원소 수인지 문자열 길이인지 정수의 값인지 비트 길이인지 밝힌다. 입력과 출력 포함 여부, 워드와 비트 모델, 원소 크기 가정을 적어 두면 서로 다른 구현의 설명을 비교할 수 있다.
다음으로 실행 중 살아 있는 자료를 나열하고 수명을 겹쳐 본다. 입력 복사, 임시 버퍼, 호출 스택, 방문 집합, 캐시와 출력 소비자의 보관 상태가 빠지지 않았는지 확인한다. 전체 할당량과 최대 동시 사용량은 따로 계산한다.
공간을 줄이는 변경에는 의미 검증을 붙인다. 공유 뷰로 바꾸어도 독립성 계약이 맞는지, DP 압축의 갱신 방향이 올바른지, 출력 복원이 필요한지, 버퍼 제한이 처리량과 오류에 어떤 영향을 주는지 살핀다. 느린 기준 해법과의 대조가 유용하다.
마지막으로 실제 환경에서 측정해 분석의 가정과 다른 원인을 찾는다. 점근 차수는 증가율을 설명하고 측정은 현재 구현의 객체·할당자·실행 조건을 보여준다. 두 방법을 함께 사용하면 단순히 “공간 O(n)”이라는 표기보다 어떤 메모리를 왜 사용하는지 설명할 수 있다.