[2022.12.19 ~ 2022.12.24] 시간복잡도 공간복잡도

시간 복잡도, 공간 복잡도

개념

• 시간 복잡도

  • 입력값의 변화에 따라 연산을 실행할 때, 알고리즘의 연산 횟수로 수행 시간을 평가합니다. (수행 시간은 실행 환경에 따라 다르게 측정되기 때문에 연산 횟수로 수행 시간을 평가)

• 공간 복잡도

  • 알고리즘 수행에 필요한 메모리 양을 평가합니다.
  • 공간 복잡도는 보조공간(Auxiliary Space)과 입력 공간(input size)을 합친 포괄적인 개념
  • 보조 공간(Auxiliary Space)은 알고리즘이 실행되는 동안 사용하는 임시 공간이기 때문에 입력 공간(input size)을 고려하지 않습니다.

시간 복잡도 표기 종류

• 시간 복잡도 표기 종류
  • Big-O(빅-오) : 상한 점근
    • 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠해볼 수 있기 때문에 주로 Big-O를 많이 사용합니다.
  • Big-Ω(빅-오메가) : 하한 점근
  • Big-θ(빅-세타) :그 둘의 평균

자바스크립트 데이터 타입별 기본 공간 복잡도

인덱스로 접근 가능하다면 O(n) 공간복잡도를 가집니다.

• booleans, numbers, undefined, null : O(1)
• strings : O(n) -> 문자열 길이
• array, objects : O(n) -> 배열이나 객체의 길이

공간 복잡도 구하는 예시

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

• 사용한 변수
  • total (number)
  • i (number)
• total과 i 모두 number로 O(1)의 공간 복잡도를 갖게 됩니다.

---

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

• 사용한 변수
  • newArr (array)
  • i (number)
• i는 number이지만, newArr은 배열로 O(n)의 공간 복잡도를 갖게 됩니다.

---

function subtotals(arr) {
  let subtotalArray = Array(arr.length);

  for (let i = 0; i < arr.length; i++) {
    let subtotal = 0;
    for (let j = 0; j <= i; j++) {
      subtotal += array[j];
    }
    subtotalArray[i] = subtotal;
  }

  return subtotalArray;
}

• 사용한 변수
  • subtotalArray (array)
  • i (number)
  • j (number)
  • subtotal (number)
• O(n)의 공간 복잡도를 갖습니다.

• 공간 복잡도 예시 2

<참고>

• 재귀함수의 경우에는 함수가 몇 번 실행되느냐에 따라 stack이 쌓이는 경우를 다루기 때문에 별도로 계산하여야 합니다.