공간복잡도 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)이다

profile
게임개발자 백엔드개발자

0개의 댓글

Powered by GraphCDN, the GraphQL CDN