알고리즘 - 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity) 알아보기

 

 

 

 

시간복잡도(Time Complexity)

시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간을 입력 크기(n)에 따라 수학적으로 표현한 것입니다.

 

 

 

시간 복잡도의 필요성

세상에는 많인 알고리즘과 해결법이 존재합니다. 프로젝트를 진행 중 A방법은 5초가 걸리지만 B방법은 2초가 걸린다고 가정합니다. 둘 다 정상적으로 작동은 하지만 이러한 알고리즘이 20개, 30개가 된다면? 입력의 수가 매우 커진다면 문제가 생길 확률이 높아집니다. 따라서 어떠한 알고리즘을 작성한다면 시간 복잡도 분석은 아주 중요합니다. 그중에서도 어떤 것이 최고인지 평가하는 방법이 시간 복잡도 분석 즉, 빅-O표기법입니다.

 

• 코드를 실행하지 않고도 알고리즘의 성능을 비교할 수 있습니다.
• 하드웨어에 의존하지 않고 알고리즘 자체의 효율성을 평가할 수 있습니다.
• 알고리즘에서 비효율적인 코드를 찾기 쉬워집니다.

 

Big-O 표기법(Big - O - Notation)

빅-O표기법은 입력 크기가 커질 때 알고리즘의 실행 시간이 증가하는 속도를 설명하는 수학적 표현입니다.

 

※빅-O표기법을 사용해 시간 복잡도를 계산할 땐 제일 빠르게 증가하는 수만 체크하는게 중요함.

ex) (n^2 * n + 2)라면 시간복잡도는 O(n^2) -> 입력값(n)이 1억이라면 n^2에 비해 n과 + 2는 아주 작은 수.

 

 

 

 

 

시간복잡도 계산하는 방법

시간 복잡도는 수동으로 측정하는 방법과 기본 연산(=, +, -, 비교, 할당 등)의 실행 횟수를 기준으로 측정합니다.

 

 

• 수동으로 측정하는 방법

function addUpTo(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

let t1 = performance.now(); // 화면이 렌더링되고 나서 시간 측정(알고리즘 실행X)
addUpTo(1000000000); // 알고리즘 실행
let t2 = performance.now(); // 알고리즘이 끝나고 나서의 시간 측정(알고리즘 종료)
console.log(`Time Elapsed: ${(t2 - t1) / 1000} seconds.`) // 소요된 시간

 

 

 

 

 

• 상수 시간 복잡도 O(1)

function addUpTo(n) {
  return n * (n + 1) / 2; //n의 수가 몇이던 *, + , / 연산 한번씩 실행함.
}

• 입력 크기와 무관하게 한 번의 연산만 실행합니다.
• *, -, / 의 연산을 1번씩 실행하기에 O(3)이 아닌, O(1)이라고 표현합니다.
• 시간 복잡도: O(1)

 

 

 

 

 

• 선형 시간 복잡도 O(n)

// 1번
function addUpTo(n) {
  let total = 0; // = 연산
  for (let i = 1; i <= n; i++) { // =연산 2, 비교 연산 n, +연산 n, 할당 n
    total += i; // +연산 n, =연산 n
  }
  return total;
}

// O(5n + 2) ??

// 2번
function countUpAndDown(n) {
  console.log("Going up!");
  for (let i = 0; i < n; i++) {
    console.log(i);
  }
  console.log("At the top!\nGoing down...");
  for (let j = n - 1; j >= 0; j--) {
    console.log(j);
  }
  console.log("Back down. Bye!");
}

 

• 입력크기(n)가 증가함에 따라 반복 횟수가 증가합니다.
• 위 1번 알고리즘에서 연산의 수를 모두 더해 시간복잡도는 O(5n + 2)라고 표현하는 것이 아닌 O(n)이라고 표현합니다.
• 2번 알고리즘에서 시간 복잡도가 O(n)인 반복문이 2개가 있다고 해서 2O(n)이 아닌 O(n)이라고 표현합니다.
• 시간 복잡도: O(n)

 

 

 

 

 

• 이중 반복문, 2차 시간 O(n^2)

function printAllPairs(n) {
  for (var i = 0; i < n; i++) { // O(n) 
    for (var j = 0; j < n; j++) { // O(n)
      console.log(i, j);
    }
  }
}

 

• 첫 번째 반복문은 n번, 두 번째 반복문도 n번이므로 O(n^2)이 됩니다.
• 시간 복잡도: O(n^2)

 

 

 

 

 

• 로그 시간 복잡도 O(log n)

이진탐색

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // 원하는 값 찾음
    } else if (arr[mid] < target) {
      left = mid + 1; // 오른쪽 절반 탐색
    } else {
      right = mid - 1; // 왼쪽 절반 탐색
    }
  }

  return -1; // 값이 없을 경우
}

 

• 입력 크기가 n일 때, 매번 작업 범위를 절반으로 줄이는 알고리즘에서 발생합니다.
• 입력값(n)에 따라서 실행 횟수의 증가가 매우 느리기 때문에 매우 효율적입니다.
• ex) 이진탐색, 이진탐색트리

 

 

 

 

 

• 로그 선형 시간 복잡도 O(n log n)

병합 정렬

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const sorted = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      sorted.push(left[i++]);
    } else {
      sorted.push(right[j++]);
    }
  }

  return [...sorted, ...left.slice(i), ...right.slice(j)];
}

 

• 병합정렬: 배열을 재귀적으로 나누고, 다시 병합하면서 정렬하는 알고리즘입니다.
• 배열을 반으로 나누는 작업은 시간 복잡도가 O(log n)입니다.
• 각 단계에서 모든 요소를 비교하면서 병합하는 과정이 이루어집니다. -> 최대 n번 -> O(n)
• 따라서, 위 알고리즘의 시간 복잡도는 O(n log n)입니다.
• 시간 복잡도: O(n log n)

 

 

 

 

 

• 배열(Array) 메서드의 시간 복잡도

연산 및 메서드	시간 복잡도	설명
접근 arr[]	O(1)	특정 인덱스에 접근하는 것은 상수시간입니다.
삽입 push()	O(1)	배열 끝에 요소를 추가하는 것은 상수 시간입니다.
삭제 pop()	O(1)	배열 끝 요소를 제거하는 것도 상수 시간입니다.
앞에 추가 unshift()	O(n)	배열 앞에 요소를 추가하면 나머지 요소를 한칸씩 뒤로 밀어내야하기 때문에 선형 시간입니다.
앞에서 제거 shift()	O(n)	배열 앞에 요소를 제거하면 나머지 요소를 한칸씩 앞로 당겨야하기 때문에 선형 시간입니다.
정렬 sort()	O(n log n)	병합정렬을 기반으로 동작하기 때문에 배열의 크기가 클 수록 효율적입니다.
검색 indexOf()	O(n)	배열을 처음부터 끝까지 순회하며 값을 탐색합니다.
검색 includes()	O(n)	특정 값이 배열에 존재하는지 확인하려면 배열을 순회하여야 합니다.
map()	O(n)	배열의 모든 요소를 순회하며 새로운 배열 생성합니다.
filter()	O(n)	배열의 모든 요소를 순회하며 조건에 맞는 요소를 새로운 배열로 반환합니다.
reduce()	O(n)	배열을 순회하며 값을 누적합니다.
forEach()	O(n)	배열을 순회하며 콜백 함수 실행합니다.
splice()	O(n)	배열의 특정 위치에서 삽입/삭제를 한다면 나머지 요소를 이동해야 합니다.
slice()	O(n)	배열의 특정 부분을 복사합니다.
concat()	O(n)	두 배열을 합칠 때 두 배열의 크기만큼 작업 필요합니다.

 

 

 

 

 

 

• 객체(Object) 메서드의 시간 복잡도

연산 및 메서드	시간 복잡도	설명
접근 (obj[key])	O(1)	객체의 특정 키에 접근하는 것은 상수시간입니다.
삽입 (obj[key] = value)	O(1)	새로운 키-값 쌍을 추가하는 것도 상수 시간입니다.
삭제 (delete obj[key])	O(1)	키-값 쌍 삭제도 상수 시간입니다.
탐색 (key in obj)	O(n)	객체의 모든 키를 순회해야 하므로 선형 시간입니다.
Object.keys(obj)	O(n)	객체의 모든 키를 배열로 반환하므로 키의 개수에 비례하는 선형 시간입니다.
Object.values(obj)	O(n)	객체의 모든 값를 배열로 반환하므로 값의 개수에 비례하는 선형 시간입니다.
Object.entries(obj)	O(n)	객체의 키-값 쌍을 배열로 반환하므로 선형 시간입니다.

 

 

 

 

 

 

 

	시간 복잡도	성능(입려 크기 증가에 따른 증가율)
	O(1)	매우 빠름
	O(logn)	비교적 빠름
	O(n)	중간
	O(n2)	느림
	O(n!)(팩토리얼)	매우매우 느림

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

공간 복잡도(Space Complexity)

시간 복잡도는 알고리즘이 시간을 얼마나 잡아먹는지 표현하는 방법이었다면, 공간 복잡도는 입력이 커질수록 얼마나 많은 공간(메모리)을 잡아먹는지 표현하는 방법입니다. 이때 입력되는 값을 제외하고 알고리즘 자체가 필요로 하는 공간만을 따집니다.

 

 

 

 

공간 복잡도 계산하는 방법

• 상수 공간 복잡도 O(1)

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

 

• 입력 값과 상관없이 두 개의 변수만 필요로 합니다.
• 공간복잡도: O(1)

 

 

 

 

• 선형 공간복잡도 O(n)

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

 

• 배열의 크기가 입력값의 따라 증가합니다
• 공간복잡도: O(n)

 

 

 

 

 

• 재귀 호출의 대한 공간복잡도 O(n)

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

 

• 재귀 함수는 호출될 때마다 스택 메모리를 사용하므로, 깊이가 깊어질수록 메모리를 더 사용합니다.
• 공간복잡도: O(n)