공간 복잡도

공간 복잡도란?

 

공간 복잡도는 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 의미한다. 즉, 알고리즘이 필요로 하는 '메모리의 양'을 의미한다고 생각하면 된다.

공간 복잡도는 '총 공간 = 고정 공간 + 가변 공간' 으로 나타낼 수 있고, 수식으로는 S(P) = c + Sp(n)으로 표현한다.

이때, 고정 공간은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구를 말한다. 즉, 코드 저장 공간이나 단순 변수, 고정 크기의 구조 변수, 상수를 뜻한다.

가변 공간은 동적으로 필요한 공간의 요구를 말한다. 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간을 의미한다.

공간 복잡도에 영향을 미치는 요소

• 변수
• 자료 구조(Data Structure)
• 함수 호출(Function Call)
• 할당(Allocation)

공간 복잡도의 주요 특징

 

입력 크기에 따른 측정

• 공간 복잡도는 일반적으로 입력 데이터 크기(n)에 따라 표현됨

빅오 표기법 사용

• O(1), O(n), O(n^2)등의 표기법으로 나타냄

시간 복잡도와의 관계

• 때로는 추가 메모리를 사용해서 실행 시간을 단축할 수 있다.

고정 공간과 가변 공간

• 고정 공간 : 입력과 출력의 횟수나 크기와 관계없는 공간. 즉, 코드 저장 공간이나 단순 변수, 고정 크기의 구조 변수, 상수를 뜻함.
• 가변 공간 : 입력 크기에 따라 변화하는 동적으로 필요한 공간. 즉, 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해 필요한 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간을 의미한다.

공간 복잡도의 종류

• 상수 공간 O(1) : 입력 크기와 관계없이 일정한 양의 메모리 사용
• 선형 공간 O(n) : 입력 크기에 비례하여 메모리 사용
• 로그 공간 O(logn) : 입력 크기의 로그에 비례하려 메모리 사용
• 이차 공간 O(n^2) : 입력 크기의 제곱에 비례하여 메모리 사용

비효율적인 코드와 효율적인 코드

def inefficient(text):
    result_list = []
    
    for i in range(len(text) -1, -1, -1):   # 글자를 맨뒤에서부터 거꾸로 하나씩 가져온다.
        result_list.append(text[i])         # 가져온 글자를 리스트에 저장한다.
        
    return ''.join(result_list)
    
print(inefficient('hello'))
# olleh

 

위의 코드는 입력받은 문자열을 뒤에서부터 하나씩 읽어서, 새로운 리스트에 하나씩 담고, 다시 합치는 방식으로 결과를 출력해준다. 지금은 입력받은 문자열이 5글자지만, 입력받는 문자열이 n글자라면 생겨나는 공간역시 n글자 짜리의 공간이 필요하므로, 이때 공간 복잡도는 O(n)이 된다.

def reverse_string_efficient(text):
    return text[::-1]

print(reverse_string_efficient("hello"))
# olleh

 

하지만 파이썬의 슬라이싱 기능을 활용해서 위와 같이 코드를 작성해준다면 결과는 동일하게 출력되지만, 새로운 리스트를 만들고 그 값을 저장해서 반환하는 절차가 사라지기 때문에 공간 복잡도는 O(1)이 된다.

시소 관계 (Trade-off)

 

시간 복잡도와 공간 복잡도는 한쪽을 최적화하면 다른 한쪽이 희생되는 시소 관계 (Trade-off)에 있다.

 

시간을 아끼고 공간을 더 쓰기 (Time-efficient, Space-consuming)

• 현재 대부분의 고성능 알고리즘이 택하는 방향.
• 매번 복잡한 연산을 새로 하는 대신, 계산 결과를 메모리에 미리 캐싱해두고 필요할 때 바로 꺼내 써서 속도를 올리는 방식이다.

공간을 아끼고 시간을 더 쓰기 (Space-efficient, Time-consuming)

• 메모리가 극도로 제한된 환경에서 사용.
• 추가 메모리를 전혀 쓰지 않고, 값을 찾을 때까지 데이터를 처음부터 끝까지 다시 돌며 계산을 반복한다.

현대 프로그래밍에서의 방향성

• 과거엔 코드가 메모리를 조금만 많이 써도 프로그램이 작동하지 않았기 때문에 공간복잡도가 우선이었음.
• 현대는 하드웨어의 발전으로 속도(레이턴시)의 기준이 훨씬 올라감.
• 따라서, 메모리(공간)를 조금 더 여유롭게 쓰더라도, 더 빠른 속도(시간)를 제공하기 위해 설계한다.

그렇다면 공간복잡도는 중요하지 않는가?

• 빅데이터 처리 : 처리해야 할 데이터가 수천만, 수억 건이 되면 보조 공간을 쓰는 것만으로도 엄청난 크기의 메모리가 사용되어 시스템이 다운(OOM, Out Of Memory)될 수 있다.
• 임베디드 및 모바일 환경 : 스마트 워치, IoT 기기, 스마트폰 앱 환경은 컴퓨터 서버만큼 메모리가 여유롭지 않다. 따라서 제한된 메모리 안에서 앱이 부드럽게 돌아가게 하기 위해 공간 최적화가 필수이다.

결국 결론은, 하드웨어가 아무리 좋아졌다 해도 좋은 개발자라면 시간 복잡도, 공간 복잡도를 항상 염두해두고, 내가 개발하고 있는 서비스가 어떤 환경에서 돌아가는지, 데이터의 총 크기는 얼마인지, 메모리는 얼마나 필요한지 모든걸 따져보고 시간과 공간의 균형을 잘 찾는 것이라 생각한다.