Udemy - Big O (빅오 표기법)

---

Big O?

💡 Big O표기법이란, 코드의 상대적 성능과 효율성을 측정할 수 있는 지표다.

1. 왜 사용해야 하는가?
   • 코드 작동과 성능에 대한 명확한 측정 척도가 필요하다.
   • 같은 솔루션 내의 서로 다른 코드의 성능을 상대적으로 비교하는데 도움이 된다.
   • 내 코드의 비효율적인 부분을 찾아서 해결할 수 있다.
   • 그리고…. 면접에 단골 출제된다…!!
2. 뭐가 더 나은 코드일까?
   • 속도가 빠른 코드 ?
     ⇒ 컴퓨터 성능에 따라 상이, 측정값이 정확하지 않다
   • 메모리 점유율이 낮은 코드 ?
   • 가독성이 좋은 코드 ?

---

Big O의 기본

컴퓨터가 처리해야 하는 작업의 횟수를 계산 (컴퓨터 하드웨어와는 무관)

1. O(1)

   ⇒ n값이 변하던 말던 처리 작업 횟수는 동일함! (일직선 수평 그래프)

2. O(n)

   ⇒ 1차함수 그래프

3. O$$(n^2)$$

   ⇒ 2차함수 그래프, 중첩 반복문

---

Big O 심플 계산법 (간소화)

1. n 앞 뒤의 사칙연산 등은 무시해도 된다.

2. 가장 큰 n제곱이 Big O의 n값이 된다.

3. 특정 조건에 따라 리턴값이 달라질 경우 ?

   무한대를 가정하고 풀면 된다.

   function logAtMost10(n) {
     // 이 경우 0~9까지는 다른 값들이 출력되는데 10부터는 계속 1~10이 출력된다.
     // 따라서 무한대를 가정하면 이 시간복잡도는 O(1)이 된다.
     for (let i = 1; i <= Math.min(n, 10); i++) {
       console.log(i);
     }
   }

---

공간 복잡도

입력값(n)이 증가함에 따라 알고리즘이 차지하는 공간이 어떻게 변하는지?
즉, 알고리즘이 차지하는 메모리에 초점을 맞춤

1. 규칙들

   1. 불린, 숫자, undefiend, null은 모두 같은 크기의 공간을 차지한다.
   2. 문자열(String)은 O(n)의 크기를 필요로 한다.
   3. 배열과 오브젝트 또한 O(n)의 크기를 필요로 한다.

2. 계산 방법

   ⇒ 선언되는 변수, 즉 차지하는 메모리에 집중한다. (시간 복잡도는 차치)
   그리고 이전과 같이 무한대를 가정하기도 한다.

   • 예시1

     function logUpTo(n) {
       // 이 경우 n값이 아무리 증가해도 메모리 공간은 "i=" 한 자리만 변화하며 필요하기 때문에
       // 이 알고리즘의 공간 복잡도는 O(1)이다.
       for (let i = 1; i <= n; i++) {
         console.log(i);
       }
     }

   • 예시2

     function onlyElementsAtEvenIndex(array) {
       var newArray = Array(Math.ceil(array.length / 2));
       // 이 경우는 array의 길이가 증가할 때마다 차지하는 공간도 커진다.
       // 따라서, 이 알고리즘의 공간 복잡도는 O(n)이다.
       for (let i = 0; i < array.length; i++) {
         if (i % 2 === 0) {
           newArray[i / 2] = array[i];
         }
       }
       return newArray;
     }

---

로그와 섹션 재생

1. 로그 복잡도의 사용 이유
   • 몇몇 검색 알고리즘에서 종종 사용된다.
   • 효율적인 정렬 알고리즘은 로그를 포함한다.
   • 재귀 알고리즘에서 로그 공간 복잡도를 사용한다.