Big O

Big O Notation ( 표기법 )

 - Big O Notation은 알고리즘이 실행되는 데 걸리는 시간 ( 시간 복잡도 ) 또는 알고리즘이 사용하는

   메모리 양 ( 공간 복잡도 )에 대해 설명하는 데 사용하는 언어입니다.

 

 - Big O는 최악의 경우인 " 상한 " 실행 속도에 중점을 둡니다.

※ 우리가 Big O 표기법을 사용할 때 " 실행 시간 "이 우리가 아는 시간 ( 초, 밀리초 등 )이 아니라는 점을 인지해야 합니다.

 

 - 실행 시간의 분석은 프로세서, 언어 또는 실행 시간 환경과 같은 특정 사항을 고려하지 않고 시간을 크기 N 의 문제를 

   완료하는 데 걸리는 작업 또는 단계의 수로 생각 할 수 있습니다.

  => Big-O 표기법은 입력 크기에 비해 런타임이 얼마나 빨리 증가하는 지 추적하는 방법입니다.

 

 - 최악의 경우에 대해 생각할 때 질문은 다음과 같습니다

  => 크기 N의 입력에 대해 발생할 수 있는 가장 많은 작업 / 단계는 무엇인가?

 

O(1) : 일정한 시간

 - O( 1 )은 입력의 크기에 관계없이 알고리즘을 실행하는 데 일정한 시간이 걸린다는 것을 의미합니다.

 

Ex ) 책갈피의 경우 " 실제 세계 "에서 일정한 시간이 어떻게 작동하는 지 보여주는 좋은 예시입니다.

        책갈피를 사용할 경우 독자가 읽은 마지막 페이지를 쉽게 찾을 수 있습니다.

 

Ex ) 프로그래밍에서의 Big - O는

 - 수학 연산

 - 인덱스를 통해 배열에 접근

 - 키를 통해 해시 접근

 - 스택에서 푸시나 팝

 - 대기열에서의 삽입 및 제거

 - 함수에서 값 반환 

등이 있습니다.

 

const smallCollection = [1, 2, 3, 4];
const bigCollection = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13];

function findFirstIndex(arr) {
  const firstIndex = arr[0];
  return firstIndex;
}

 - 위의 findFirstIndex의 경우 어떤 크기의 배열이 들어오든 O( 1 )의 동일한 런타임이 생성됩니다.

 - firstIndex의 반환은 상수 ( 1 )의 시간 연산이기도 합니다. N의 크기에 관계없이 이 두 작업 모두 일정한 시간이 걸리게

   됩니다.

 

O(n) : 선형 시간

 - O ( n )의 경우엔 입력과 동일한 속도로 실행 시간이 증가함을 의미합니다.

 

Ex ) 책을 읽는 행위는 " 현실 세계 "에서 선형 시간이 어떻게 작동되는지 보여주는 예입니다.

        책 한 페이지를 읽는 데 1분이 걸린다고 하면 30 Page는 30분 100 Page는 100분이 걸리게 됩니다.

        1000 페이지에 달하는 분량의 책을 다 읽지 못할 수 있지만 우리는 최악의 경우 1000분이 걸리게 될 것을 미리 알 수

        있습니다.

 

Ex) 프로그래밍에서 가장 일반적인 선형 시간 연산 중 하나는 배열을 순회하는 것입니다.

       JavaScript의 forEach, map, reduce와 같은 메서드는 처음부터 끝까지 전체 데이터 컬랙션을 실행합니다.

const smallCollection = [1, 2, 3, 4];
const bigCollection = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13];

function printAllValues(arr) {
  for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
  }
}

 - 위의 printAllValues의 함수의 경우 N을 반복하는 데 필요한 작업 수는 N의 크기와 직접적인 관련이 있습니다.

 - 일반적으로 말해 루프를 보는 것은 검사 중인 특정 코드 덩어리에 대해 O ( N )의 런타임을 가지고 있다는

   좋은 지표입니다.

 

const numbers = [2, 3, 4, 5, 6, 7, 8, 9];

const LtThree = numbers.find((number) => number < 3);
console.log(LtThree);

 - 하지만 find 메소드 같은 경우 전체 배열을 통해 실행되지 않기 때문에 선형 검색으로 볼 수 없을까요?

 - 위의 예시 같은 경우 3보다 작은 값은 0번째 인덱스에 있습니다.

   => 이는 O ( 1 )로 볼 수 있지 않을까요?

 

const numbers = [2, 3, 4, 5, 6, 7, 8, 9];
const worst_numbers = [3, 4, 5, 6, 7, 8, 9, 2];
const LtThree = numbers.find((number) => number < 3);

 - 저희는 최악의 시나리오에대해 생각해야된다는 것을 항상 기억해야 합니다.

 - 찾는 값이 항상 맨 앞에 이상적으로 위치하고 있는 것이 아닌 배열의 마지막 값에 있을 수도 있다는 것을 가정하고

   바라보아야 합니다.

 - 위의 경우 3보다 작은 값을 찾기 위해선 모든 배열을 반복해야 합니다.

 - find의 경우 O (N)으로 보아야 될 것입니다!!

 

O( n² ) : 이차의 시간

 - O ( n² )은 계산이 입력 데이터 크기의 제곱인 2차 시간으로 실행됨을 의미합니다.

 - 프로그래밍에서 기본적인 정렬 알고리즘의 대부분은 최악의 경우 실행 시간이 O ( n² )입니다.

 

 - 버블 정렬

 - 삽입 정렬

 - 선택 정렬

const smallCollection = [1, 2, 3, 4];
const bigCollection = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13];

function countOperations(arr) {
  let operations = 0;

  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      operations++;
    }
  }
  return operations;
}
console.log(countOperations(smallCollection)); // 16

 - countOperations의 경우 반복 후 operations 변수를 증가시키는 두개의 중첩 for문이 있습니다.

 - smallCollection 같은 경우는 16개의 작업으로 끔찍하진 않지만 N이 거대한 컬랙션인 경우 10억 * 10억의 경우

   1000조 또는 1,000,000,000,000,000,000입니다...

 - 배열의 크기가 1,000개에 불과하더라도 백만 개의 연산을 생성하게 됩니다.

 

O ( log N ) : 로그 시간

 - O ( log N )의 경우 입력 크기의 Log 에 비례하여 실행 시간이 증가한다는 것을 의미합니다.

 - 입력을 기하급수적으로 늘리더라도 시간은 거의 증가하지 않습니다.

 

Ex ) 

 - 실제 사전에서 샘플 크기를 절반으로 줄여가며 단어를 찾는 것은 " 현실 세계 "에서 대수 시간이 어떻게 작동하는지

   보여주는 훌륭한 예시가 될 수 있습니다.

 - 예를 들어 "Senior"라는 단어를 검색할 때 사전의 정확히 가운데를 열고 " S "로 시작하는 단어가 현재 보고 있는

   페이지에 앞인지 뒤인지 확인할 수 있습니다.

 - 책의 뒷부분에 S가 나온다고 판단된다면 앞부분은 더이상 보지 않아도 됩니다.

   이런 과정을 반복하는 알고리즘을 따르면 단어를 찾을 때까지 검색해야하는 페이지 수를 매번 2분의 1로 줄일 수

   있습니다.

 - 프로그래밍에서 물리적 사전을 통해 검색하는 이러한 행위는 이진 검색 작업의 한 예입니다.

   로그 실행 시간을 논의할 때 사용되는 가장 일반적인 방법입니다.

 

const smallNumber = 1000;
const biggerNumber = 10000;

function countOperation(n) {
  let operations = 0;
  let i = 1;

  while (i < n) {
    i = i * 2;
    operations++;
  }
  return operations;
}
console.log(countOperation(smallNumber)); // 10
console.log(countOperation(biggerNumber)); // 14

 - N은 입력 ( 숫자 ) 또는 입력된 배열의 크기가 될 수 있습니다.

 - 위의 예에서 n = 2000이면 11개의 작업으로 끝나게 됩니다. n = 4000이면 12개의 작업으로 끝나게 됩니다.

   n의 양을 두 배로 늘릴 때 마다 연산의 양은 1만 증가하게 됩니다.

 - 대수 시간에 실행되는 알고리즘은 입력이 커질 수록 더 큰 의미를 갖게 됩니다.

   log(7)은 3가지 작업을 log(1000000)의 경우는 20개의 작업만 거치면 됩니다!!

참고: 종종 O(log n)과 혼동되는 O(n log n)은 알고리즘의 실행 시간이 선형 및 로그 복잡도의 조합인 선형 연산임을 의미합니다.
분할 정복 전략을 사용하는 정렬 알고리즘은 다음과 같이 선형입니다.

* 병합 정렬
* 팀소트
* 힙 정렬

시간 복잡도를 볼 때 O(n log n)은 O(n2)와 O(n) 사이에 위치합니다.

---

Big O 계산하기

1. 상수 삭제하기

const numbers = [1, 2, 3, 4, 5];

function logEverythingTwice(itmes) {
  for (let i = 0; i < itmes.length; i++) {
    // O(N)
    console.log(itmes[i]); // O(1)
  }
  for (let i = 0; i < itmes.length; i++) {
    // O(N)
    console.log(itmes[i]); // O(1)
  }
}

logEverythingTwice(numbers);

 - Big-O는 런타임이 얼마나 빨리 증가하는지에 관한 것이기 때문에 기억할 첫 규칙은 알고리즘을 분석 할 때 상수를

   삭제하는 것입니다.

 

 - 위의 예의 경우 배열(선형)의 길이를 반복하는 두 개의 개별 루프가 존재합니다.

   각 루프는 각 배열의 요소를 console로 찍어냅니다. 우리는 일정 시간에 바로 실행되는 연산에 대해 관심을 갖지 않기에

   두 루프만 고려하여 O (2n)의 빅오 노테이션을 갖게 됩니다. 하지만 2마저도 상수이므로 이것을 O ( N )이라고 합니다.

 

const numbers = [1, 2, 3, 4, 5];

function logEverythinFiveTimes(items) {
  for (let i = 0; i < items.length; i++) {
    // O(N)
    for (let j = 0; j < items.length; j++) {
      // O(N)
      console.log(items[i]); // O(1)
    }
  }
}

 - 하지만 위처럼 루프가 중첩될 경우 각 요소를 두 번 로깅하지 않고 다섯 번 씩 로깅하게 됩니다.

   이런 경우 실행 시간을 더하지 않고 곱하게 됩니다.

 - 결국 O( n * n )으로 O( n² )을 제공하게 됩니다.

 

 - 우리는 성능을 위해 중첩 루프는 무조건 피하는 것이 좋습니다.

 - 하지만 작은 데이터 셋이나 다차원 배열 조작 등 써야하는 상황에 처할 수 있습니다. 그 때 수행하는 작업에 따라

   성능에 영향을 미칠 수 있다는 것을 알고 있어야 합니다.

 

2. 비 지배적인 ( 영향력 없는 항 ) 항은 삭제하기

function printMultiplesThenSum(items) {
  for (let i = 0; i < items.length; i++) {
    // O(N)
    for (let j = 0; j < items.length; j++) {
      // O(N)
      console.log(items[i]); // O(1)
    }
  }
  const sum = items.reduce((acc, item) => {
    // O (N)
    return (acc += item); // O(1)
  }, 0);
  return sum; // O(1)
}

 - printMultiplesThenSum에서 상수를 삭제한 후 함수에 대한 표기법은 O( n² + n)임을 알 수 있습니다.

   하지만 Big-O의 경우 비 지배항에도 관심이 없으므로 n을 삭제하게 됩니다.

 => 즉 O ( n² + n )의 경우 O (  n² )이 됩니다.

300 => 300 * 300 + 300 에서 300은 너무 미미합니다..

 

---

결론

 - Big - O를 이해하지 않더라도 코드를 작성하는 데는 아무 문제 없지만 알고리즘을 설계할 때 런타임 환경 간 효율적인

   코딩이 중요하므로 알아야합니다!!

ps
빅오(O)는 상한을 의미한다. 
하한을 의미하는 빅오메가, 평균을 의미하는 빅세타가 있지만 보통 빅오만을 사용한다.

빅오 표기법은 시간 복잡도 외에도 공간 복잡도를 표현하는데 널리 쓰인다. 

알고리즘은  "시간과 공간이 트레이드오프 관계이다" (트레이드 오프 : 하나가 증가하면 다른 하나는 감소한다.)

즉, 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행 시간이 느리다는 것이다. 
물론, 아닌 알고리즘도 드물게 존재하지만 대부분 의 경우 트레이드오프 관계가 성립되며 이는 알고리즘의 주요한 특징 중 하나이다.

---

 

Big-O Notation: A simple explanation with examples

 

빅오 표기법 (O, big-O)

 

Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell