[JS] 시간 복잡도(Time Complexity), 공간 복잡도(Space Complexity)

알고리즘 계산 복잡도는 다음 두 가지 척도로 표현할 수 있다.

 

• 시간 복잡도 : 얼마나 빠르게 실행되는가
• 공간 복잡도 : 얼마나 많은 저장 공간이 필요한가

 

시간 복잡도는 코드를 처리하는 데 얼마의 시간이 걸리는지 알려준다. 이런 알고리즘의 시간 복잡도는 주로 빅-오 표기법을 사용하여 나타낸다. 

 

Big-O(빅-오)란 알고리즘의 성능을 수학적으로 표현해주는 표기법이다. 이를 통해 알고리즘의 시간과 공간 복잡도를 표현할 수 있다.

빅오 표기법은 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하기 위해 사용한다.  

 

시간 복잡도(Time Complexity)

 

 

O(1) : Constant Time

O(1)은 입력 데이터의 크기에 상관없이 일정한 시간이 걸리는 알고리즘을 O(1)이라 말한다.

function twoUp(num) {
  return num+num;
}

num에 어떤 수가 들어와도 + 한번의 연산을 시도한다. 연산이 여러 번 시행되도 시간 복잡도는 O(1)로 동일하다.

 

 

O(n) : Linear Time

O(n)은 입력 데이터의 크기에 비례해서 처리시간도 늘어나는 알고리즘을 표현할 때 사용한다. 

function count(num) {
  let count = 0;
  for(let i = 1; i <= num; i++){
    if(i%2 === 1) {
      count += 1;
    }
  }
  return count;
}

O(1)과 다르게 num에 할당되는 값에 따라 반복하게 되고, n값이 1000이라면 1000만큼 반복하게 된다. 즉, num만큼 순회하므로 O(n)으로 표기할 수 있다. 여러개의 for문이 있어도 O(n)으로 표기한다.

 

 

 

O(n^2) : Quadratic Time

입력 데이터의 크기의 제곱만큼 처리시간이 걸리는 알고리즘을 표현할 때 사용한다.

function matrix(num) {
  const mat = [];
  for(let i = 0; i < num; i++){
    const row = [];
    for(let j = 0; j < num; j++) {
      row.push([i,j]);
    }
    mat.push(row);
  }
}

위 코드에서 num이 100이라고 하면 이중 for문이기 때문에 i = 0 일때 j가 100번 반복하게 되므로 총 10000번 반복하게 된다. 

 

 

 

 

O(log n)

이진 탐색 등의 알고리즘을 표현할 때 사용한다.

let arr = [];

function log(k, s, e){
  for(let i = s; i <= e; i++){
    arr.push(i);
	let m = (s+e)/2;
    
    if(arr[m] === k){
      console.log(m) 
    } else if(arr[m]> k){
      return log(k, s, m-1);
    } else{
      return log(k, m+1,e)
    }
  }
}

 

이진 검색이 대표적인 알고리즘이다. 만약 정렬된 배열에서 특정 숫자를 찾을 때, 이진 검색을 이용한다면 배열의 가운데 값과 키값을 비교한다. 만약 배열의 가운데 값이 키값보다 작다면, 키값보다 작은 값들은 볼 필요가 없다. 그럼 다시 없어진 배열 값을 제외한 요소들 중에서도 중간값을 찾아서 키값과 비교한다. 이렇게 한번 처리할 때마다 검색해야 하는 데이터의 양이 절반씩 떨어지는 알고리즘을 O(log n) 알고리즘이라 한다.

---

공간 복잡도(Space Complexity)

 

프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함

 

총 필요 저장 공간

• 고정 공간(알고리즘과 무관한 공간) : 코드 저장 공간, 단순 변수 및 상수 (문제의 인스턴스(입출력 크기)에 무관, 일정한 양의 메모리 공간)
• 가변 공간(알고리즘 실행과 관련있는 공간) : 실행 중 동적으로 필요한 공간 (문제의 인스턴스에 따라 가변적인 메모리 공간)
• S(P) = c + Sp(n) => c: 고정 공간 / Sp(n) : 가변공간

빅오 표기법을 생각해볼 때, 고정 공간을 상수이므로 공간 복잡도는 가변 공간에 좌우된다.

 

공간 복잡도 계산은 알고리즘에서 실제 사용되는 저장 공간을 계산하고 이를 빅오 표기법으로 표현할 수 있으면 된다.