[Algorithm] 알고리즘 공간복잡도에 대하여

공간복잡도란?

공간복잡도(Space Complexity)란 프로그램의 성능을 분석하는 방법 중 하나로, 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법입니다. 하지만 최근에는 컴퓨터 성능의 발달로 인해 메모리의 여유 공간이 충분하다못해 넘치기 때문에 공간복잡도의 중요성이 예전에 비해서 많이 낮아졌습니다. 시간복잡도의 경우 알고리즘을 잘못 구성하였을 경우 결과값이 나오지 않거나 현저하게 느린속도가 나오기에 최근에는 공간복잡도보다는 시간복잡도를 우선시하여 프로그램을 작성합니다.

 

[Algorithm] 알고리즘 시간복잡도에 대하여

 

공간복잡도 계산법 (빅-오)

int a = 10;

일반적으로 공간이 하나씩 생성되는것을 1이라고 표현합니다. 위의 공간복잡도는 O(1)입니다.

 

for(int i=0;i<input;i++){
    int a = 10;
}

반복문이 N번만큼 반복하므로 위의 공간복잡도는 O(n)입니다.

 

for(int i=0;i<input;i++){
    int a = 10;
}
for(int i=0;i<input;i++){
    int a = 10;
}

N번만큼 반복하는 반복문이 2개가 있습니다. 착각할 수도 있지만 O(n²)이 아닌 O(n)입니다. 공간 복잡도 계산에는 가장 큰 영향을 미치는 알고리즘 하나만 계산합니다. 반복문이 하나가 있으나 2개가 있으나 수십개가 있으나 O(n)입니다.

 

for(int i=0;i<input;i++){
    for(int j=0;j<input;j++{
        int a = 10;
    }
}

 N번만큼 반복하는 이중 for문이 있으므로 위 소스의 공간 복잡도는 O(n²)입니다.

 

for(int i=0;i<input;i++){
    for(int j=i;j<input;j++{
        int a = 10;
    }
}

위의 경우에는 내부 for문의 변수 j의 값이 i 이므로 엄연히 이중 for문보다 시간이 적게 걸리지만 그래도 시간 복잡도는 O(n²)입니다. 공간 복잡도 계산에서는 정확한 값을 산출하는 것이 아니라 근사치를 계산하기 때문입니다.

 

for(int i=0;i<input;i++){
    for(int j=i;j<input;j++{
        int a = 10;
    }
}
for(int i=0;i<input;i++){
    int a = 10;
}

이중 for문 1개와 for문 1개가 있습니다. 이때는 영향을 더 많이 끼치는 이중 for문 하나만 계산하여 공간 복잡도는 O(n²)입니다.

 

공간복잡도를 줄이는 방법

공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 동적할당을 한다면 얼마만큼의 동적할당이 예상되는지, 재귀함수라면 재귀호출을 몇번이나 하는지 등이 공간 복잡도에 영향을 미칩니다.

​프로그램에 필요한 공간은 크게 두가지로 나눌 수 있습니다.

1. 고정 공간
2. 가변 공간

 

시간적인 측면을 무시하고 공간복잡도만을 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료구조들을 사용하는것이 효율적입니다. 또 함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요합니다. 특히 재귀 함수같은 경우에는 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소 를 저장할 공간이 필요하기 때문에 ​만약 재귀적(Recursive)으로도 짤 수 있고 반복문으로도 짤 수 있는 상황에는 반복문으로  짜는게 더 효율적이라고 볼 수 있습니다.

댓글(0)

Designed by JB FACTORY