공간복잡도

공간복잡도 Space Complexity
알고리즘 수행에 필요한 저장공간의 양

공간 복잡도 예제

public int factorialFunc(int n)
{
	int fac = 1;
    for(int idx = 2; idx < n+1; ++idx)
    {
    	fac = fac*idx;
    }
    return fac;
}

위의 반복문을 활용한 팩토리얼 함수에서는 int n, int fac, int idx 변수들이 사용됨
n의 값이 변해도 추가로 더 필요한 메모리가 없다. 따라서 공간복잡도는 항상 일정하다
O(1)으로 계산할 수 있다

public int factorialFunc(int n)
{
	if(n > 1)
    {
    	return n * factorialFunc(n-1);
    }
    else
    {
    	return 1;
    }
}

위의 재귀형태의 팩토리얼 함수는 재귀함수 호출할때마다 int n이 추가로 할당된다
n의 값이 증가할때마다 int n이 추가로 할당된다. 따라서 공간 복잡도는 O(n)이다