Big O 표기법

실행 시간 측정

코드의 성능을 분석할 때 실행 시간을 직접 재는 방법은 비효율적입니다. 기기마다 성능이 다르고 측정 방법도 제각각이기 때문입니다. 무엇보다 오래 걸리는 코드를 일일이 측정하기는 매우 번거롭습니다.

Big O 표기법

이 문제를 해결하려고 Big O 표기법을 씁니다. Big O 표기법은 알고리즘의 효율성을 나타내며, 다음 특징이 있습니다.

• 입력 크기에 따라 코드가 몇 번 실행되는지가 연산 개수보다 중요하다
• 전체적인 추세에만 관심이 있으므로 최고차항만 신경 쓰면 된다

삽입 정렬 코드는 이중 반복문 구조입니다. 외부 루프는 n-1번 돌고 내부 루프는 최악의 경우 i번씩 돌기 때문에 총 n×(n-1)/2번 비교합니다. 입력 크기가 커질수록 최고차항이 지배하므로 시간 복잡도는 최종적으로 O(n²)이 됩니다.

const insertionSortV1 = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j >= 0; j--) {
      if (arr[j] < arr[j - 1]) swap(arr, j, j - 1);
      else break;
    }
  }
  return arr;
};

O(n²)은 그다지 좋은 성능이 아닙니다.

아래 차트를 보면 각 시간 복잡도별 성능 차이를 한눈에 확인할 수 있습니다.