Algorithm 19장 - 시간복잡도와 공간복잡도

Algorithm

시간복잡도

Big-O

• 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 말한다.
• 시간 복잡도는 3가지 표기법이 있으며, 표기법에 따라 최악,최선,중간(평균)을 나타낸다.
  • Big-O(빅-오)
  • Big-Ω(빅-오메가)
  • Big-θ(빅-세타)
• 최악의 경우도 고려하여 대비하기 위해 Big-O 표기법을 주로 사용한다.

Big-O 표기법의 종류

O(1)

• 입력값이 증가하더라도 시간이 늘어나지 않는다.
• 입력값의 크기와 관계없이 즉시 출력값을 얻을 수 있다.

function O_1_algorithm(arr, index) {
  return arr[index];
}

let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2

O(n)

• 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 말한다.
• 입력값이 1일 때 1초가 걸린다면, 입력값이 100일 때 100초가 걸리는 알고리즘을 말한다.
• another_O_n_algorithm이 2초씩 증가한다고 하여도 O(2n)이 아닌 O(n)으로 표기한다.
• 같은 비율로 증가하고 있다면 2배,5배,10배로 증가하여도 O(n)으로 표기한다.

function O_n_algorithm(n) {
  for (let i = 0; i < n; i++) {
    // do something for 1 second
  }
}

function another_O_n_algorithm(n) {
  for (let i = 0; i < 2n; i++) {
    // do something for 1 second
  }
}

O(log n)

• 자료구조의 이진트리와같이 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.
• BST의 값 탐색도 같은 로직을 가진 O(log n)이다.
  • 1~100 중 하나의 숫자를 플레이어1이 고른다 (30을 골랐다고 가정합니다).
  • 50(가운데) 숫자를 제시하면 50보다 작으므로 down을 외친다.
  • 1~50중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다.
  • 25보다 크므로 up을 외친다.
  • 경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다.

O(n²)

• 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가한다.
• 입력값이 1일 때 1초가 걸리고, 5일 때 25초가 걸리는 경우를 말한다.
• 2n과 5n을 모두 O(n)이라고 표기하는 것처럼, n³과 n⁴도 모두 O(n²)으로 표기한다.

function O_quadratic_algorithm(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // do something for 1 second
    }
  }
}

function another_O_quadratic_algorithm(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        // do something for 1 second
      }
    }
  }
}

O(2ⁿ)

• Big-O 중 가장 느린 시간 복잡도를 가진다.
• 재귀로 구현하는 피보나치 수열이 가장 대표적인 예이다.
• 아래와 같은 함수에 n이 40이어도 수초가 걸리며, n이 100이상이면 평생 반환받지 못할 수도 있다.

function fibonacci(n) {
  if (n <= 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

공간 복잡도

• 알고리즘이 수행되는 데 필요한 메모리의 총량을 말한다.
• 프로그램이 필요로 하는 메모리 공간을 산출하는 것을 의미한다.
• 변수 n에 따라 n개가 만들어지며, 재귀함수로 1까지 호출할 경우 n부터 1까지 쌓이게 된다.
• 따라서 해당 함수의 공간 복잡도는 O(n)이라 볼 수 있다.

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