어느 알고리즘 이든 다음과 같은 이유들로 컴퓨터의 메모리를 필요로 한다.

  1. 프로그램 명령어 저장
  2. 상수 저장
  3. 변수 저장
  4. 기타 등등

알고리즘의 공간복잡도는 다음과 같이 정의할 수 있다.

알고리즘이 수행되는데 필요한 메모리의 총량

 

프로그램이 실행될 때 보통 세가지 이유로 컴퓨터 메모리를 사용한다.

  1. Instruction Space: 컴파일된 명령어들을 저장하는 메모리의 양
  2. Environmental Stack: 함수 호출시 부분적으로 실행 된 함수의 정보를 저장하는 데 사용되는 메모리의 양
  3. Data Space: 모든 변수와 상수를 저장하는 메모리의 양

알고리즘의 공간복잡도를 분석할 때, 보통 Instruction Space와 Environmental Stack은 무시하고 Data Space만을 고려한다. 변수, 상수, 구조체 등이 저장되는데 필요한 메모리만을 계산하겠다는 뜻이다.

 

예시 1

int square(int a) {
    return a*a;
}

위 코드에서는 변수 'a'를 저장하는데 2바이트, return value를 위해 2바이트가 사용된다. input값 'a'에 대해 4바이트가 고정적으로 필요하다.


알고리즘이 어느 input value에 대해 항상 고정된 공간을 필요로 할 때, 이를 상수 공간 복잡도(Constant Space Complexity)라 한다.

 

예시 2

int sum(int A[], int n){
	int sum = 0, i;
	for(i = 0; i < n; i++)
		sum = sum + A[i];
	return sum;
}

A[]를 저장하기 위해 'n*2' 바이트, n을 저장하기 위해 2바이트, 지역변수 sum, i를 위해 각각 2바이트씩, return value를 위해 2바이트가 필요하다. 즉, 이 코드를 수행하기 위해 '2n + 8' 바이트가 필요하며 인풋인 n에 메모리 양이 의존하게 된다.


알고리즘이 어느 input value가 증가함에 따라 필요한 공간이 선형적으로 증가하는 것을 선형 공간 복잡도(Linear Space Complexity)라고 한다.

 


'Data Structure' 카테고리의 다른 글

Time Complexity - 시간복잡도  (1) 2018.04.19

+ Recent posts