어느 알고리즘 이든 다음과 같은 이유들로 컴퓨터의 메모리를 필요로 한다.
- 프로그램 명령어 저장
- 상수 저장
- 변수 저장
- 기타 등등
알고리즘의 공간복잡도는 다음과 같이 정의할 수 있다.
알고리즘이 수행되는데 필요한 메모리의 총량
프로그램이 실행될 때 보통 세가지 이유로 컴퓨터 메모리를 사용한다.
- Instruction Space: 컴파일된 명령어들을 저장하는 메모리의 양
- Environmental Stack: 함수 호출시 부분적으로 실행 된 함수의 정보를 저장하는 데 사용되는 메모리의 양
- 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 |
---|