[백엔드TIL] 공간복잡도에 대한 이해 (67일차)

프로그램 복잡도

• 프로그램 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음
  • 시간 복잡도: 얼마나 빠르게 실행되는지
  • 공간 복잡도: 얼마나 많은 저장 공간이 필요한지

좋은 프로그램은 실행 시간도 짧고, 저장 공간도 적게 쓰는 프로그램 (=알고리즘)

• 통상 둘 다를 만족시키기는 어려움
  • 시간과 공간은 반비례적 경향이 있음
  • 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
  • 그래서! 알고리즘은 시간 복잡도가 중심
  • 하지만, 공간 복잡도는 기본이기 때문에 기본이 안되서 떨어지는 경우도 많습니다! </aside>
• 공간 복잡도와 시간 복잡도 모두 빅 오 표기법으로 표현한다. = O(n)

1) O(n) 공간 복잡도 예시

1️⃣ n! 팩토리얼 구하기

• 재귀 함수를 통해서 구현하므로 변수 n에 따라서 변수 n이 n개가 만들어지게 됨
• factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1까지 스택에 쌓이게 됨
• 따라서 공간 복잡도는 O(n)

public int factorial(int n) {

    if(n == 1) {
        return n;
    }

    return n*factorial(n-1);
}

2️⃣ 배열에서 n인덱스 이전까지 합 구하기

• 사용되는 변수는 a[], n,result,i 이다.
• ( a[]의 n개의 원소를 저장할 공간 ) + ( 변수 n,i,result를 위한 공간 ) 이 필요하다. a[]가 n보다 큰 공간을 할당해야하므로 O(n) 만큼의 공간 복잡도가 필요하다.
  
  
  정리 

공간복잡도를 줄이는 방법

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

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

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

 

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