공간 복잡도

시간 복잡도(Time Complexity)는 인풋 크기에 비례하는 알고리즘의 실행 시간을 나타냅니다. 시간 복잡도를 잘 이해하셨다면 공간 복잡도도 어렵지 않습니다.

 

공간 복잡도(Space Complexity)는 인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 나타냅니다. 물론 공간 복잡도도 점근 표기법으로 표현할 수 있기 때문에 간편하게 Big-O 표기법을 사용할 수 있습니다.

 

간단한 예시 몇 가지만 봅시다.

 

O(1)

def product(a, b, c):
    result = a * b * c
    return result

파라미터 a, b, c가 차지하는 공간을 제외하면 추가적으로 변수 result가 공간을 차지합니다. result가 차지하는 메모리 공간은 인풋과 무관하기 때문에 함수 product의 공간 복잡도는 O(1)입니다.

 

O(n)

def get_every_other(my_list):
    every_other = my_list[::2]
    return every_other

인풋 my_list의 길이를 n이라고 합시다.

 

파라미터 my_list가 차지하는 공간을 제외하면 추가적으로 변수 every_other가 공간을 차지합니다. every_other가 차지하는 공간은 어떻게 표현할 수 있을까요?

 

리스트 every_other에는 my_list의 짝수 인덱스의 값들이 복사돼서 들어갑니다. 약 n/2​개의 값이 들어간다는 거죠. O(n/2​)은 O(n)으로 나타낼 수 있기 때문에, get_every_other 함수의 공간 복잡도는 O(n)입니다.

 

O(n^2)

def largest_product(my_list):
    products = []
    for a in my_list:
        for b in my_list:
            products.append(a * b)
    
    return max(products)

인풋 my_list의 길이를 n이라고 합시다.

 

파라미터 my_list가 차지하는 공간을 제외하면 추가적으로 변수 products, a, b가 공간을 차지합니다. 우선 a와 b는 그냥 정수 값을 담기 때문에 O(1)이겠죠? 그렇다면 products가 차지하는 공간은 어떻게 표현할 수 있을까요?

 

리스트 products에는 my_list에서 가능한 모든 조합의 곱이 들어갑니다. 그렇다면 총 n^2 개의 값이 들어가겠죠? 따라서 largest_product의 공간 복잡도는 O(n^2)입니다.

 

 

출처 코드잇