[알고리즘] 시간 복잡도와 빅오(Big O) 계산법

📄 시간 복잡도

프로그래머스 문제를 푸는데 이제 점점 성능을 고려해야할 필요성이 생겼습니다.
효율성 테스트를 넘어가야 하기 때문이죠. 🥶
똑같은 답일지라도 빨리 답이 나오는 코드가 더 좋은 성능을 가진 코드인데 이를 구별할 수 있게 하는 것이 시간 복잡도입니다.

시간 복잡도는

입력 값에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는 지 알려주는 지표입니다.

이 시간 복잡도를 나타내주는 방법 중 하나가 빅오(Big O) 표기법입니다.

O(1)는 입력값에 상관없이 정해진 스텝의 계산을 실행합니다.

콘솔을 한번만 찍는 함수는 아무리 큰 입력값이 오더라도 계산에 영향을 끼치지 않습니다.

const constantComplexity = (arr) => {
  console.log("hello");
};

constantComplexity([1, 2, 3, 4, 5]);

O(n)는 입력값이 증가함에 따라 시간이 같은 비율로 증가합니다.

const linearComplexity = (n) => {
  for(let i = 0; i < n; i++>){
    ...
  }
}

O(n)는 입력값이 증가함에 따라 시간이 n²으로 증가합니다.

const quadraticComplexity = () => {
  for (let i = 0; i < n; i++) {
    for (let j =0; j < n; j++) {
      ...
  }
}

O(n)는 입력값에 따라 처리 시간이 증가합니다.

O(n)은 입력 값이 1이 될 때까지 절반으로 나누는 작업을 반복합니다.
따라서 입력값에 따라 처리 시간이 증가하지만, 비례해서 증가하는 것이 아니므로 O(1)다음으로 빠른 계산법입니다.