[알고리즘]공간 복잡도

앞선 게시물에서 시간 복잡도의 bigO표기법에 대해 정리하였다. 정리한 게시물

이번에는 공간 복잡도에 대해 정리해보자.

 

알고리즘 성능 평가

어떤 알고리즘이 있을 때, 그 알고리즘의 성능 평가는 어떻게 할 수 있을까?

알고리즘 성능을 평가하기 위해 '복잡도(Complexity)'의 척도를 사용한다.

시간 복잡도와 공간 복잡도가 있으며 복잡도가 낮을수록 좋은 알고리즘이다.

시간 복잡도: 특정한 크기의 입력에 대해 알고리즘의 수행 시간 분석
공간 복잡도: 특정한 크기의 입력에 대해 알고리즘의 메모리 사용량 분석

쉽게 말하자면,

시간 복잡도는 입력이 커질수록 알고리즘의 실행 속도가 어떻게 바뀌는지 분석하고,

공간 복잡도에서는 입력이  커질수록 알고리즘이 얼마나 많은 공간을 차지하는지 분석하는 것이다. 

 

공간 복잡도는 보조 공간(auxiliary space)과 입력 공간(input space)을 합친 포괄적인 개념이다.

보조 공간(auxiliary Space)은 알고리즘이 실행되는 동안 사용하는 임시 공간이다. 알고리즘 자체가 필요로 하는 공간을 의미한다.

입력 공간(input space)은 제쳐두고 보조 공간(auxiliary Space)에 중점을 두자.

 

몇 가지 규칙들을 살펴보자.

1. 대부분의 원시 요소(booleans, numbers, undefined, null)들은 상수 공간이다. 즉, 불변 공간이다.

    입력의 크기와는 상관없이, 숫자가 1이든 1000이든, true든 false든 똑같은 공간을 차지한다. 

 

2. 문자열은 O(n)만큼의 공간이 필요하다. 만약 50자라면 1자인 문자열보다 50배 더 많은 공간을 차지한다.

 

3. 참조 타입(reference type), 배열과 객체 또한 O(n)의 공간을 차지한다. n은 배열의 길이나 객체 키의 개수일 수 있다.

    만약 배열의 길이가 4라면 배열의 길이가 2인 배열보다 2배 더 많은 공간을 차지한다. 

 

예시를 보자.

function sum(arr) {
    let total = 0;
    for(let i = 0; i <= arr.length; i++) {
        total += arr[i];
    }
    return total
}

여기서 집중해야 할 건 시간 복잡도가 아닌 공간 복잡도이다.

sum함수는 배열을 받아서 해당 배열의 길이만큼 값들을 모두 더하는 기능을 한다.

 

배열의 길이와 상관 없는 total변수 -one number

루프를 반복하며(시간은 상관X) 생성되는 변수 i = 0 -another number

 

total변수로 다시 돌아오지만 시간이 걸릴 뿐이기에 중요하지 않다. 입력의 크기가 차지하는 공간과는 아무 상관없다.

total과 i 두 변수만 존재하기 때문이다. 배열의 길이에 따라 새로운 변수에 더하는 것도 아니고 total변수에 더할 뿐이며 새로운 변수를 만들지 않는다. 결국 상수 공간이 있다는 것을 의미하며 O(1) 공간이다. 

 

function double(arr) {
    let newArr = [];
    for(let i = 0; i <= arr.length; i++) {
        newArr.push(2 * arr[i]);
    }
    return newArr;
}

double함수는 변수 newArr에 배열을 담도록 선언하였고 입력받은 배열의 길이만큼 배열을 추가(push)해준다.

대신 arr의 값에 *2를 하여 push하여 newArr에 추가된다.

위 코드에서 배열의 크기가 늘어나서 무한대에 가까워질수록 공간 복잡도는 어떻게 되는가?

 

입력된 배열의 길이가 10이면 새로운 배열에 저장되는 아이템이 10개가 되어 리턴된다.

그렇기에 차지하는 공간은 입력된 배열의 크기와 비례해서 커지기 때문에  newArry는 O(n)의 공간을 차지한다.

let newArr = []; 이렇게 새 변수를 만드는 것은 신경 쓸 필요가 없다. O(n)으로 단순화할 수 있다. 

 

Math.ceil(.95);    // 1
Math.ceil(4);      // 4
Math.ceil(7.004);  // 8
Math.ceil(-0.95);  // -0
Math.ceil(-4);     // -4
Math.ceil(-7.004); // -7

Math.ceil() 함수는 주어진 숫자보다 크거나 같은 숫자 중 가장 작은 숫자를 integer로 반환합니다.

 

function onlyElementAtEvenIndex(arr) {
  let newArr = Array(Math.ceil(arr.length / 2));
  for(let i = 0; i <= arr.length; i++) {
    if(i % 2 === 0) {
      newArr[i / 2] = arr[i];
    }
  }
  return newArr;
}

console.log(onlyElementAtEvenIndex([1, 2, 3, 4]))

만약 배열의 길이가 4라면 Array(2)가 newArry가 반환된다. 즉 newArr.length가 2이고 newArr[0]은 undefined이다.

for문을 살펴보면 i값이 0, 1, 2, 3, 4 이렇게 들어온다. 만약 i % 2 === 0일 때 if문 안의 내용을 실행하는데 먼저 0이 들어온다.

0은 참이므로 arr[0]의 값인 1이 newArr[0/2]즉 newArr[0]에 들어가고, 1은 false이므로 건너뛰고, newArr[2/2] = arr[2]가 실행되어 newArr[1]에 3이 들어간다. 3은 false이므로 건너뛰고, newArr[4/2] = arr[4]가 실행되는데 arr[4]는 존재하지 않아, newArr[2]에 undefined가 들어간다.

실행 결과

위 코드의 공간 복잡도는 O(n)이다. 

 

function subtotals(arr) {
  let subtotalArr = Array(arr.length);
  for(let i = 0; i <= arr.length; i++) {
    let subtotal = 0;
    for(let j = 0; j <= i; j++) {
   	  subtotal += arr[j]
  	  }
  	subtotalArr[i] = subtotal;
	}
  return subtotalArr;
}

위 코드 또한 O(n)의 공간 복잡도이다.

 

 

log(logarithm)

어떤 알고리즘들은 O(1), O(n), O(n제곱)처럼 빅오가 간단하지 않은 경우가 있다. 빅오 표기법 중에 수학 개념들이 포함되어 있을 수 있다. 그중 자주 나오는 개념이 로그(log)이다. what is a log?

 

로그함수는 지수함수의 역함이다. 나누기와 곱하기가 짝인 것처럼 로그함수와 지수함수는 짝이다. 이게 무슨 말인가?

x = log_ab를 정의하자면, a를 b로 만드는 지수는 x라는 것이다.

log₂(8) = 3 은 2³= 8이라는 의미이다. 로그함수는 항상 2를 밑으로 하는 것은 아니다. 큰 그림을 이해하는 것이지 밑이 중요한 것이 아니다.

 

로그를 계산하는 규칙을 살펴보자.

어떤 이진 로그를 대략 계산하기 위해서는 그 숫자가 1보다 작아지기 전에 2로 나눠지는 횟수이다.

8을 보면, 8 / 2 = 4, 1보다 더 크죠? 그래서 다시 4 / 2 = 2 아직 1보다 더 크다. 2 / 2 = 1

총 3회를 나눈다. log(8) = 3이 된다. 25는 정확하게 나눠지지 않죠. 정확하게 2로 나눌 방법이 없다. 

25/2 = 12.5, 12.5 / 2 = 6.25, 6.25 /2 = 3.125, 3.125 / 2 = 1.5625, 1.5625 / 2 = 0.78125  총 5회

즉, log(25)는 대략 4와 5회 사이에 있다는 것을 알 수 있다. 정답은 log(25) = 4.64이다.

 

실제 계산은 중요하지 않고, 그래프에 어떻게 보이는지 이다. 

수학으로 계산하는 것을 걱정할 것이 아니라 로그가 무엇이고 로그의 복잡도의 성능을 알고 있어야 한다.

탐색 알고리즘, 효율적인 정렬 알고리즘, 재귀에서 로그를 다시 접하게 될 것이다.

재귀에서는 시간이 아니라 공간 복잡도와 관련되어 있다. 

 

전체적으로 정리해보자면,

- 알고리즘의 성능을 분석하기 위해서는 Big O Notation을 사용한다. 실행 시간과 공간 복잡도가 어떻게 변하는지.

- Big O Notation은 정확도가 아닌 전체적인 주체를 중요하게 생각한다.

선형(linear)? 2차(quadratic)? 상수(constant)?

- 시간과 공간 복잡도(Big O로 측정되는)는 알고리즘에만 의존하며 알고리즘을 실행하는 데에 사용되는 하드웨어에 영향받지 않는다.

어느 알고리즘을 일반 컴퓨터와 슈퍼컴퓨터에서 실행하는 속도는 실제 차이가 있겠지만, Big O는 실행될 연산의 개수를 따지기 때문에 전체적인 주체는 다르지 않을 것이다.