Algorithm # 시간복잡도

📝오늘배운내용

빅오(Big-O) 표기법

O(1) 시간복잡도

입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸린다.
O(1) 시간복잡도를 가지는 알고리즘은 아래와 같다.

function algorithm(arr, idx) {
  return arr[idx];
}

let arr = [1, 2, 3, 4];
let idx = 1;
let result = algorithm(arr, idx);
console.log(result); // 2

O(n) 시간복잡도
입력 데이터의 크기에 비례해서 처리시간이 걸린다.
데이터가 커질수록 처리시간도 늘어난다.
O(n) 시간복잡도를 가지는 알고리즘은 아래와 같다.

function algorithm(n) {
  for (let i = 0; i < n; i++) {
    // code
  }
}

function algorithm2(n) {
  for (let i = 0; i < 2n; i++) {
    // code
  }
}

O(log n) 시간복잡도
Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
경우의 수를 절반으로 계속 줄여나가며 답을 찾는 알고리즘이다.

O(n2) 시간복잡도

입력 데이터의 크기가 증가함에 따라 시간이 n의 제곱수의 비율로 증가한다.
예시로, 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸린다면, 이 알고리즘의 시간 복잡도는 O(n2)라고 할 수 있다.
O(n2) 시간복잡도를 가지는 알고리즘은 아래와 같다.

function algorithm(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // code
    }
  }
}

O(2n) 시간복잡도

Big-O 표기법 중 가장 느린 시간 복잡도이다.
재귀로 구현하는 피보나치 수열은 O(2n)의 시간복잡도를 가지는 대표적인 알고리즘이다.

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