Big O 표기법

🌟 실행 시간 측정

코드의 성능을 분석하기 위해 실행 시간을 직접 측정하는 것은 비효율적인 일입니다.
기기마다 성능도 다르고 시간을 측정하는 방법도 다 다르기 때문입니다. 무엇보다 2시간 동안 실행하는 코드를 직접 실행해서 측정하는 건 매우 귀찮은 일이죠.

---

🌟 Big O 표기법

이런 문제를 해결하기 위해 Big O 표기법을 사용합니다. Big O 표기법은 알고리즘의 효율성을 표기 해주는 표기법으로, 다음과 같은 특징을 가집니다.

• 연산의 개수를 측정하는 것보다 Input에 따라 코드가 몇 번 실행됐는지가 더 중요하다.
• 전체적인 추세에만 관심이 있으므로 최고차항만 신경쓰면 된다.

삽입 정렬 코드를 한 번 보겠습니다. 이중 반복문 구조이기 때문에 외부 루프는 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²)은 그다지 좋은 성능은 아닌 것 같습니다.

출처:  https://www.researchgate.net/figure/Big-O-time-complexity-chart-based-feature-selection-a-Big-O-complexity-chart-b-Time_fig3_371457259