[Week10] 시간복잡도와 공간복잡도

시간 복잡도

• 알고리즘이 수행되는 데 걸리는 연산 횟수를 데이터 크기(n)에 따라 수학적으로 표현한 것
• 예시

for (let i = 0; i < n; i++) {
  console.log(i);
}
// n번 반복 -> 시간 복잡도 : O(n)

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    console.log(i, j);
  }
}
// 이중 반복 -> n * n 번 실행 -> 시간복잡도 : O(n²)

공간 복잡도

• 알고리즘이 사용하는 메모리 양을 데이터 크기(n)에 따라 수학적으로 표현한 것
• 예시

function makeArray(n) {
  const arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(i);
  }
  return arr;
}
// 크기 n인 배열을 만듦 -> 공간 복잡도 : O(n)

function sum(n) {
  let total = 0;
  for (let i = 0; i < n; i++) {
    total += i;
  }
  return total;
}
// 변수만 하나 사용 -> 공간 복잡도 : O(1)

정리