파이썬 공간복잡도

시간 복잡도가 인풋 크기에 비례하는 알고리즘 실행 시간을 나타냈다면, 공간 복잡도도 마찬가지로 인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 나타낸다. 공간 복잡도도 점근 표기법으로 표현할 수 있다.

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의 공간은 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에 가능한 모든 조합의 곱이 들어가기 때문에 largest_products의 공간 복잡도는 O(n^2)이다.

O(1) 공간복잡도, O(n^2) 시간복잡도:

def largest_product(my_list):
	max = my_list[0] * my_list[0]
    	for a in my_list:
        	for b in my_list:
            		if (a * b) > max:
                    		max = a * b
	return max

공간 복잡도와 시간 복잡도는 항상 비례한 것은 아니다. 위의 products 내용 대신에 최댓값만 변수에 저장하면 시간 복잡도는 여전히 O(n^2)이지만 공간 복잡도는 O(1)이 된다. 시간 복잡도는 O(n^2)이지만 공간 복잡도는 O(1)이 된다.