빅오 표기법(Big O Notation)

간단한 실행 시간 체크하기

기능적으로 performance.now()는 현재 시각을 나타내는 정밀한 시간 값을 제공합니다.
이 값은 페이지 로드 또는 특정 이벤트에서 측정된 시간 간격 등을 측정할 때 유용합니다.
이를 통해 코드 실행 또는 네트워크 요청과 같은 작업에 소요된 시간을 정확하게 측정할 수 있습니다.

var startTime = performance.now();

// 측정하려는 작업 실행
// 예: 어떤 계산 또는 함수 실행

var endTime = performance.now();
var elapsedTime = endTime - startTime;

console.log("작업 수행 시간: " + elapsedTime + "밀리초");

what does better code mean
Faster and Less memory-intensive, More readable

---

Big O 표기법

Big O 표기법은 알고리즘의 효율성을 표현하는 방법 중 하나로,
어떤 일을 할 때 걸리는 시간이나 사용되는 메모리의 양을 나타냅니다.
이것은 주로 알고리즘의 복잡도를 표현하는 데 사용됩니다.

굳이 왜 Big O Notation 이 있어야 하나?
컴퓨터마다 성능이 다르고 코드 성능 테스트를 할때
쉽게 검증할 수 있기 때문이라고 생각합니다.

시간 복잡도

간단한 설명을 읽고 밑에 예시 코드가 있으니 참고하시길 바랍니다.

1. O(1) - 상수 시간
   입력이 어떻게 커지든 상관없이 실행 시간이 항상 일정합니다.
   예를 들어, 어떤 목록에서 첫 번째 항목을 찾는 것은 항상 똑같은 시간이 걸립니다.
   코드 : (f(n) = 1) <- 입력 값과는 상관 없이 실행 시간이 무조건 1이다.

2. O(log n) - 로그 시간
   입력이 두 배로 늘 때마다 실행 시간이 한 단계 늘어납니다.
   예를 들면 정렬된 목록에서 특정 항목을 찾는 것이 여기에 해당합니다.

3. O(n) - 선형 시간
   입력이 늘어날 때마다 실행 시간도 비례해서 늘어납니다.
   예를 들면 목록에서 항목을 찾는 것이나 목록의 항목들을 모두 한 번씩 확인하는 것이 여기에 해당합니다.
   코드 : (f(n) = n) <- 즉 입력에 따라 실행 시간도 같이 늘어난다.

4. O(n^2) - 제곱 시간
   입력이 늘어날 때 실행 시간은 입력 크기의 제곱에 비례해서 늘어납니다.
   예를 들어, 두 목록을 비교하여 정렬하는 알고리즘이 여기에 해당합니다.
   코드 : (f(n) = n^2) <- 입력에 따라 실행시간이 제곱으로 늘어난다.

5. O(2^n) - 지수 시간
   입력이 하나 늘어날 때마다 실행 시간이 지수적으로 늘어납니다.
   이는 일반적으로 효율적이지 않은 알고리즘입니다.

이렇게 표현된 복잡도는 주로 알고리즘이 얼마나 효율적으로 동작하는지에 대한 척도로 사용됩니다.
간단히 말해서, Big O가 작을수록 알고리즘이 더 효율적으로 동작합니다.

시간 복잡도 예시 코드

function addUpTo(n) {
  return n * (n + 1) / 2;
}

//연산이 3번 이루어 진다. -> O(1) 이다. 상수 시간 복잡도

function addUpTo(n) {
  let total = 0;
  for (let i = 0; i <= n; i++) {
     total += 1;
  }
  return total;                     
}

/* O(n) 이다. 선형 시간 복잡도이며 n의 개수에 따라 연산이 n 번 일어난다.*/

function addUpTo(n) {
  console.log("올라갑니다.");
  for (let i = 0; i <= n; i++) {              
     console.log(i);
  }
  console.log("내려갑니다.");
  for (let j = n - 1; j >= n;  j--) {
     console.log(j);
  }
}

// -> O(n) 이 2개여도 결국 O(n) 이다.

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

// -> O(n^2) 즉 제곱 시간 복잡도

Big O 표기법을 사용할 때 기본적으로 알아야 하는 꿀팁

1. 산수는 상수이다. 덧셈, 나눗셈, 곱셈, 뺄셈이 이에 해당한다. 2 + 2 나 100만 + 2 나 컴퓨터가 처리하는 시간은 같다.
2. 변수 배정(할당) 도 상수이다. 컴퓨터가 변수에 값을 배정하는데 걸리는 시간이 비슷하다.
3. 배열의 인덱스를 이용해서 아이템을 찾는 것도 똑같은 시간이 걸린다.
4. 시간 복잡도는 loop 에 의해서 변화된다.
5. O(n^2 + 5n + 8) = O(n^2) 이다.

공간 복잡도

공간 복잡도는 종종 Big O 표기법을 사용하여 표현되며, 주로 입력 크기에 따른 공간 사용량을 나타냅니다.
O(n)이라면 입력 크기 n에 비례하여 공간 사용량이 증가한다는 것을 의미합니다.
예를 들어, 배열이나 객체에 n개의 요소가 있다면, O(n)의 공간 복잡도를 가진다고 말할 수 있습니다.

알고리즘은 주어진 문제를 해결하기 위해 수행하는 일련의 명령이나 규칙의 집합입니다.

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

이 코드에서 반복문은 배열의 길이에 비례하여 실행되므로 시간 복잡도는 O(n)입니다.
배열의 크기가 두 배로 늘어나면 반복 횟수도 두 배로 늘어나기 때문입니다.