[codeit] Algorithm 공간 복잡도 (Space complexity)

저번 시간복잡도에 이어 이번에는 공간 복잡도에 대해 소개드리려고 합니다.

 

공간복잡도란?

공간 복잡도(Space Complexity)는 인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 나타냅니다. 

 

공간복잡도는 예제를 통해 보겠습니다.

O(1)

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

파라미터 a, b, c가 차지하는 공간을 제외하면,

result 라는 변수에는 a * b * c 라는 값은 인풋값과 무관하기 때문에 공간복잡도는 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는 my_list의 짝수 인덱스에 해당하는 값이 들어갑니다. 그러므로 n/2개의 값이 공간에 들어가게 됩니다.

따라서, O(n/2)라고 볼 수 있습니다. 하지만! Big-O 표기법에 의해서 결국에는 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)

a, b 는 일시적으로 정수를 담는 변수이기 때문에 O(1)입니다.

products 라는 빈리스트에는 a * b 에 대해서 n^2개의 값이 들어가게 됩니다.

따라서 이 알고리즘의 공간복잡도는 O(n^2)입니다.