빅오 표기법(Big O notation)

Big o 표기법

• 불필요한 연산을 제거하여 알고리즘의 성능을 평가하기 위해 사용한다.(최악인 경우를 평가)
• 측정되는 복잡도 시간 복잡도와 공간 복잡도가 있다.
• 코드가 느려지거나 장애 발생 시 비능률적인 코드를 특정해 애플리케이션의 문제점을 찾는 데 도움이 된다.

특징

1. 상수항을 무시한다
   ex) $O(n+3) => O(n)$
2. 계수를 무시한다
   ex) $O(3n) => O(n)$
3. 최고차항만 표기한다
   ex) $O(3n^2+2n+5) => O(n^2)$

시간 복잡도

• 프로세스가 수행해야하는 연산을 수치화 한 것
  (시간 기준이 아닌 것은 컴퓨터 하드웨어 성능 및 여러 조건에 의해 조금씩 달라 질 수 있기 때문에)
  

$O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(N^3) < O(2^n)$

(우측으로 갈 수록 효율⬇️😞)

Big o 표기법 종류

1. $O(1)$ - 상수시간
   : 입력 데이터에 관계 없이 일정
   ex) stack -push/pop

2. $O(log N)$ - 로그 시간
   : 데이터의 로그에 비례해 알고리즘의 단계가 늘어날 때, 알고리즘이 로그 시간으로 실행
   (연산이 한 번 실행될 때 마다 데이터의 크기가 절반 감소, 지수가2)
   ex)이진트리

3. $O(N)$ - 선형 시간
   : 데이터의 크기가 커지는 만큼 같은 비율로 늘어남
   ex)for문

4. $O(N logN)$ - 선형 로그 시간
   :로그 시간 복잡도와 선형 시간 복잡도를 곱한 만큼커짐
   (입력 데이터가 많아질수록 처리 시간이 로그 배만큼 더 늘어남)
   ex)퀵 정렬(Quick Sort),병합 정렬(Merge Sort),힙 정렬(Heap Sort)

5. $O(N^2)$ - 2차시간 , 다항
   :알고리즘의 복잡도는 n의 제곱에 정비례
   ex)삽입 정렬(Insertion Sort), 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 이중 for 문

6. $O(2^n)$ - 지수시간
   : 최악의 시간 복잡도로 주로 재귀적으로 수행하는 알고리즘
   ex)피보나치 수열, 재귀가 역기능할 경우

공간 복잡도

• 알고리즘의 실행을 완료할 때까지 필요한 자원의 양 (고정 공간, 데이터 구조 공간, 임시 공간의 메모리)를 얼마나 사용하는지 확인
• Big o 표기법 사용 가능
• JS에서
  • $O(1)$ => Booleans, numbers, undefined, null
  • $O(n)$ => String, array, object

//ex01 => Number constant space => O(1)
const sum = (array) => {
  let total = 0; //number
  for (let i = 0; i < array.length; i++) {
    total += array[i]; // number
  }
  return total;
}; 

//ex02 => Array 배열이 커질 수록 return되는 new Array 커짐 O(n)

const double = (array) => {
  let newArr = []; // array 입력 값에 따라 배열의 크기가 커지게됨
  for (let i = 0; i < array.length; i++) {
    newArr.push(array[i]); 
  }
  return newArr; // n numbers
};