공간복잡도 핵심만 짚고 넘어가기
공간복잡도 핵심만 짚고 넘어가기 — #공간복잡도 AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다 공간복잡도 이전글을 ...
#공간복잡도
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다
공간복잡도
이전글을 통해서 시간복잡도에 대해 공부해 보았습니다. 시간복잡도는 실행 코드가 걸리는 "시간"의 관점에서 효율성을 고려하는 것을 의미하는데요. 오늘 다뤄볼 공간복잡도는 "공간"의 관점에서 알고리즘을 다뤄보고자 합니다.
우리가 작성하는 코드는 실제 메모리의 한 공간을 차지합니다. 우리눈에 보이진 않지만, 컴퓨터가 알아서 메모리 공간에 저장하고, 저장된 메모리를 읽습니다.
| a = 10 |
|---|
이렇게 변수를 선언하면 공간이 하나씩 소모된다고 생각하시면 됩니다. 변수뿐 아니라 배열, 리스트와 같은 자료구조들도 메모리를 차지하게 됩니다.
공간복잡도는 전체 알고리즘 코드가 얼마나 많은 메모리 공간을 사용하는지를 고려하는 방법입니다. 알고리즘에 할당된 변수, 배열, 리스트 등을 고려하여 최대한 메모리를 덜 사용하는 쪽으로 코드를 작성하는 것이 효율적인 알고리즘이 됩니다.
빅오표기법으로 공간복잡도 분석하기
빅오표기법
시간복잡도와 마찬가지로 빅오표기법을 사용하여 공간복잡도 분석이 가능합니다. 시간복잡도에서 표기법에 대한 설명을 자세하게 해두었으니 안보신 분들은 보고 오시면 도움이 됩니다!
오늘은 정말 간단하게 분석가능한 O(1), O(n), O(n²)에 대해서만 다뤄보도록 하겠습니다.
O(1)
| # pythona = 10 |
|---|
앞에 다뤘던 코드의 공간 복잡도는 O(1)입니다.
| # pythondef space(n): i = 0 result = 0 for i in range(n): result += i return result |
|---|
많은 블로그에서 찾아볼 수 있는 대표적인 예시코드입니다. 해당 코드는 함수안에 for문이 반복되지만, 결국 함수는 result값 하나만을 호출하기 때문에 공간복잡도는 O(1)입니다.
O(n)
O(n)은 n값 만큼 공간이 n개 늘어나는 공간복잡도입니다.
| # pythondef space(n): i = 0 list = \[\] for i in range(n): list.append(i) return list print(space(4))# result\[0, 1, 2, 3\] |
|---|
리스트의 요소 하나 하나는 모두 메모리 공간을 차지합니다. n의 값에 따라 배열의 요소가 n개 생성되어 공간복잡도는 O(n)입니다.
O(n²)
O(n²)은 n값 만큼 공간이 n²개 늘어나는 공간복잡도입니다.
| # pythondef space(n): i = 0 list = \[\] for i in range(n): row = \[\] for j in range(n): row.append(j) list.append(row) return list print(space(3))# result\[\[0, 1, 2\], \[0, 1, 2\], \[0, 1, 2\]\] |
|---|
n의 값에따라 nxn배열이 만들어지면서. n²의 값을 갖게됩니다.
공간복잡도 시행착오
공간복잡도를 설명하는 코드를 만들었지만 적절하지 못한 예시를 사용하였습니다. 해당코드는 현재 수정해두었으며 수정전과 후가 어떤 차이가 있는지 정리해 보았습니다. 공간복잡도의 개념을 좀 더 이해하는데 도움이 될까 싶어서 남겨봅니다.
수정전
| # pythondef space(n): i = 0 list = \[\] for i in range(n): row = \[\] for j in range(n): row.append(j) list.append(row) break return list# result\[\[0, 1, 2\], \[0, 1, 2\], \[0, 1, 2\]\]# list = \[row, row, row\] i = 0 일때의 row만 존재# list = \[\[0, 1, 2\], \[0, 1, 2\], \[0, 1, 2\]\]# list\[0\]\[1\] = 100 변화를주면# list = \[\[0, 100 2\], \[0, 100, 2\], \[0, 100, 2\]\]# 해당 코드의 시간복잡도# row = \[ 0, 1, 2 \] # 2\3 -> 2\n -> O(n) = n + 1\*n |
|---|
해당 코드의 문제점은 j내부에서 row를 append로 추가한 후 break문을 사용하여 반복(= i)을 탈출하게 만들었습니다. 따라서 i = 0인 값에서만 j가 0, 1, 2로 순환하기에 list에 들어있는 모든 row는 같은 공간을 가진 동일한 배열이됩니다.
이 경우 list의 공간복잡도 n과, row의 공간복잡도 n이 더해져 총 2n의 공간복잡도를 가지며 최종 표기는 O(n)이 되겠습니다.
수정후
| # pythondef space(n): i = 0 list = \[\] for i in range(n): row = \[\] for j in range(n): row.append(j) list.append(row) return list# result\[\[0, 1, 2\], \[0, 1, 2\], \[0, 1, 2\]\]# list = \[row0, row1, row2\] i = 0, 1, 2 # list = \[\[0, 1, 2\], \[0, 1, 2\], \[0, 1, 2\]\]# list\[0\]\[1\] = 100 변화를주면# list = \[\[0, 100 2\], \[0, 1, 2\], \[0, 1, 2\]\]# 해당 코드의 시간복잡도# list = \[row0, row1, row2\]# row0 = \[0, 1, 2\]# row1 = \[0, 1, 2\]# row2 = \[0, 1, 2\]# n + n x n = n + n² = O(n²) |
|---|
코드를 수정하여 j문이 끝나면 row를 list에 넣었습니다. row를 i = 0, 1, 2일때 각각 row0, row1, row2라고 칭하였습니다. 해당 row는 모두 다른 공간에 위치한 개별적인 배열이됩니다.
공간복잡도는 list = n, row = n x n 으로 n + n²인 O(n²)이 됩니다.