시간복잡도

우리는 프로그램의 성능을 정확히 알지 못한다.

• 입력 크기
• 하드웨어, 운영체제 성능
• 컴파일러 최적화

이러한 고려해야 할 점이 많기 때문이다.
그래서 대략적인 성능을 비교하기 위한 상대적인 표기법을 사용한다.

빅오표기법 (Big-O notation)

실행 속도
O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(n!)

각각 어떻게 다른지 알아보자.

O(1)

일정한 복잡도라고 하며, 입력값(N)이 증가해도 실행시간은 동일하다.
ex) stack의 push, pop

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(log N)

연산이 한 번 실행될 때 마다 데이터의 크기가 절반 감소하는 알고리즘 (log의 지수는 항상 2)
ex) binary search 알고리즘, tree 형태 자료구조 탐색

for(let i = 1; i <= n; i *= 2) {
  ...
}

O(N)

입력값(N)이 증가함에 따라 실행시간도 선형적으로 증가하는 알고리즘
ex) 1중 for문

for(let i = 0; i < n; i += 1) {
  ...
}

O(N log N)

O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 상태
ex) 퀵, 병합, 힙 정렬

for(let i = 0; i < n; i += 1) {
  for(let j = 1; j <= n; j *= 2) {
    ...
  }
}

O(N^2)

O(N)의 알고리즘이 두 번 중첩된 상태
ex) 2중 for문, 삽입/버블/선택 정렬

for(let i = 0; i < n; i += 1) {
  for(let j = 0; j < n; j += 1) {
    ...
  }
}

O(2^N)

빅오 표기법 중 가장 느린 시간 복잡도로 주로 재귀적으로 수행하는 알고리즘이 이에 해당
ex) 피보나치 수열

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

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스
nana-moon님 velog
hanamon님 블로그