시간 복잡도

알고리즘의 스피드는 "완료까지 걸리는 절차의 수" 로 측정할 수 있고, 이를 시간복잡도라고 한다.

절차(= 연산)는 데이터의 할당, 비교, 증감, 계산, 반환(return)을 모두 포함한다.

알고리즘에 입력된 데이터를 N 이라 했을 때 계산식을 정의하고, 최고차항만을 남겨 시간복잡도를 파악하는 표기법을 빅오표기법이라 한다.

(최고차항만을 남기지만 앞서 붙어있는 상수에 대해서는 고려하지 않는다)

const foo = (arr: [], N: number) => {
  // cnt 데이터 할당 + 1
  const cnt = 0;
  
  // i 데이터 할당 + 1
  for (let i = 0; i < N; i++) {

    // N번 회귀하면서 i와 N을 비교, i 증가, 5로 나누고, 0과 비교하고, cnt 증가 => N * 5
    if(arr[i] % 5 === 0) cnt++;
  }
  
  // cnt 반환 + 1
  return cnt;
}

위 함수의 연산을 정의 하면 1 + 1 + 5N + 1 = 5N + 3 이라 할 수 있고, "N에 비례한다" 고 표현할 수 있다.

빅오표기법에 적용하면 O(N) 이라 정의하여 표기하는 것이다. 이외에도 다른 유형의 빅오표기법을 확인 할 수 있다.

 

 

- O(1): 주어진 데이터에 상관없이 특정 상수에 따라 작동하는 함수일 경우(상수 함수)

const foo = (arr) => {
  console.log(arr[0]);
}

 

 

- O(N): 선형 검색 알고리즘, 주어진 데이터의 길이만큼 연산하는 경우,

  정렬된 배열에 새로운 요소를 추가하는 경우(인덱스별로 값을 비교해야 하기 때문에)

const foo = (arr) => {
  for(let = 1; i < arr.length; i++) {
    console.log(i);
  }
}

 

- O(N^2): 중첩 반복문일 경우

const foo = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    for (let e = 0; e < i; e++) {
      print(e);
    }
  }
}

 

- O(logN): 정렬된 배열 데이터에서 이진 탐색을 활용하는 경우

예를 들어 전화번호부에서 이름을 찾을 때 첫장부터 찾는게 아니라 중간부터 확인하면서 검색 범위를 절반씩 줄여나가는 방식이 있다.

식으로 표현하자면,
주어진 데이터의 길이가 N이었을 때 첫 시행 후 남은 자료의 개수는 N * 1/2
두번째 시행 후 N * 1/2 * 1/2
세번째 시행 후 N * 1/2 * 1/2 * 1/2
....
K번째 시행 후 N * (1/2)^K
계속 시행하면 결국 하나의 데이터만 남게될테니까
N * (1/2)^K = 1

양쪽에 2^K 를 곱하면
N = 2^K

그리고 양쪽에 로그를 취하면
logN = K

그리고 K는 시행횟수(시간복잡도)를 의미한다.