공간복잡도

Created At

2022/01/25 23:21

Updated At

2022/03/14 09:51

분류

기타

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

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

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

O(1)

def product(a, b, c):
    result = a * b * c
    return result
Plain Text
복사

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

O(n)

def get_every_other(my_list):
    every_other = my_list[::2] # a[start : end : step]
    return every_other
Python
복사

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

파라미터 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)
Plain Text
복사

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

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

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