[Algorithm] Space Complexity (공간복잡도)

JAsmine_log·2024년 2월 29일

Time Complexity & Space Complexity

컴퓨터사이언스에서는 문제를 해결하는 여러가지 알고리즘이 있는데, 어떤 것이 가장 최적인지 비교하기 위한 방법이 필요하다. 시간복잡도와 공간복잡도는 trade-off 관계다.

기계와 configurations 과는 독립적
인풋에 대한 직접적인 관계를 보여줌
두 개의 알고리즘을 명확하게 구분할 수 있음

Space Complexity

공간복잡도는 알고리즘이나 데이터구조에서 문제를 풀때 사용되는 메모리의 공간의 양으로, 입력의 특성과 함수의 인스턴스를 의미한다. 메모리는 알고리즘 실행이 완료될 때까지의 양을 의미한다.
여기에는 입력 공간(input space)이라고 하는 입력에 사용되는 메모리 공간과 실행 중에 사용되는 다른 (보조) 메모리가 포함되며, 이를 보조 공간(auxiliary space=temporary space)이라고 합니다.
by wikipedia

Input Space
Auxiliary Space = the extra space or temporary space

Space Complexity Example

만약 size n의 행렬을 만들면 공간은 $O(n)$ 이 필요하고, 2D 행렬을 만든다면, $O(n^3)$ 이 필요하다.
일반적인 정렬 알고리즘을 비교한다고 예를 들어 볼 수 있다. 보조 공간이 공간 복잡도 보다 좋은 예가 될 수 있다. 머지 정렬(Merge Sort)가 O(n)의 보조 공간을 사용하고, 삽입 정렬(Insertion sort)과 힙 정렬(Heap Sort)은 O(1)을 사용한다. 이 알고리즘의 총 공간 복잡도는 O(n)이다.

Code & Memory & Data structure

Code(source code) : 프로그래밍 언어로 작성한 텍스트 파일
Data Structure(자료구조) : 데이터를 저장하고 관리하는 방식
Memory(메모리) : 데이터를 저장하는 공간

(그림:TCP school)

코드(code) 영역
실행할 프로그램의 코드가 저장되는 영역으로 텍스트(code) 영역
CPU가 코드 영역에 저장된 명령어를 하나씩 가져가 처리
데이터(data) 영역
프로그램의 전역 변수와 정적(static) 변수를 저장하는 영역
프로그램의 시작과 함께 할당되며, 프로그램이 종료되면 소멸
스택(stack) 영역
함수 호출과 관계되는 지역 변수와 매개변수를 저장하는 영역
함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸
스택 프레임(stack frame)은 스택 영역에 저장되는 함수의 호출 정보
스택 영역
푸시(push)하여 데이터를 저장하고, 팝(pop) 으로 데이터를 호출
후입선출(LIFO, Last-In First-Out) 방식으로, 가장 늦게 저장된 데이터가 가장 먼저 나옴
메모리 주소는 높은 주소에서 낮은 주소 방향으로 할당
힙(heap) 영역
사용자가 직접 관리하여 메모리 공간이 동적으로 할당되고 해제됨
메모리 주소는 낮은 주소에서 높은 주소의 방향으로 할당