[알고리즘] 빅오 표기법 (Big O Notation)

📌 코드 시간 재기

코드가 실행되는 데 걸리는 시간을 알 수 있는 가장 쉬운 방법은 내장 되어있는 타이밍 함수를 사용하는 것

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

let time1 = performance.now();
addUpTo(1000000000)
let time2 = performance.now();

console.log(`Time Elapsed: ${(time2 - time1) / 1000} seconds.`) 
// 1000분의 1초 단위로 되어있기 때문에 1000을 나눠 줌

그러나 코드가 실행될 때의 시간을 측정하는 것은 정확도에 문제가 있다.

  🚫   기기 사양에 따라 시간이 다르게 측정되기 때문에 정확한 시간을 알 수 없다.
  🚫   같은 기기에서도 코드를 실행할 때마다 조금씩 시간이 다르게 기록된다.
  🚫   매우 짧은 시간 안에 처리되는 빠른 알고리즘에서는 타이밍 함수가 그런 작은 차이를 정확히 측정하지 못한다.

❗️ 대신에 컴퓨터가 처리해야하는 연산 개수를 세면 된다!
어떤 컴퓨터를 사용하든 그 연산 개수는 변하지 않기 때문에 시간을 측정하는 것보다 정확하다.

✨ 예시1

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

이 경우, n값과는 상관 없이 총 3번 연산한다.
(곱셈 1번 + 덧셈 1번 + 나눗셈 1번)

✨ 예시2

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

코드	연산 횟수
let total = 0	total 선언 및 할당 (1회)
let i = 1	i 선언 및 할당 (1회)
i <= n	반복할 때마다 비교 (n회)
i++	반복할 때마다 덧셈 (n회)
i++	반복할 때마다 할당 (n회)
total += i	반복할 때마다 덧셈 (n회)
total += i	반복할 때마다 할당 (n회)

5n + 2 번 연산하는 함수로, n이 커질 수록 연산의 개수도 비례적으로 증가한다.

만약 n이 10이라면 ?
n회 반복되는 연산 총 50개 + 반복문 바깥 연산 2개 = 52개

---

📌 빅오 표기법 Big O Notation

알고리즘의 효율성(시간 복잡도)를 나타낼 때 사용하는 표기법
입력의 크기와 실행 시간 사이의 관계를 뜻한다.

일반적으로 실행시간이 가질 수 있는 최대치, 즉 가장 높은 실행 시간 값을 말한다.

• f(n) could be linear (f(n) = n)
  ➡️ 실행 시간이 선형으로 증가할 수 있다. (n과 함께 증가)

• f(n) could be quadratic (f(n) = n²)
  ➡️ 실행 시간이 n의 제곱일 수 있다. (n과 함께 증가)

• f(n) could be constant (f(n) = 1)
  ➡️ 실행 시간이 상수 일 수 있다. (n이 커져도 실행 시간에는 영향이 없음)
  ❗️ 실행 시간이 상수인 경우, 단순히 1이라고 표현한다

• f(n) could be something entirely different!
  ➡️ 입력의 크기와 실행시간 사이의 관계가 완전히 다를 수 있다.

시간복잡도 효율 순
O(1) < O(log n) < O(n) < O(n log n) < O(n²)

💡 O(1)

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

해당 함수의 경우 언제나 연산이 3개이기 때문에 O(1) 으로 표현할 수 있다.

💡 O(n)

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

해당 함수의 경우 실행 시간이 1:1 비율로 증가하고, 연산의 갯수가 n의 곱과 연결 되어있기 때문에 O(n) 으로 표현할 수 있다.

 function countUpAndDown(n) {
    console.log("Going up!");
    for (let i = 0; i < n; i++) {  // O(n), n이 증가할 수록 반복 횟수가 증가하기 때문에
        console.log(i);
    }
    console.log("At the top!\nGoing down...");
    for (let j = n - 1; j >= 0; j--) {  // O(n), n이 증가할 수록 반복 횟수가 증가하기 때문에
        console.log(j);
    }
    console.log("Back down. Bye!");
}

반복문이 2개이기 때문에 O(2n) 이라고 생각할 수 있지만 빅오 표기법으로는 O(n) 으로 표기 한다.
❗️ 같은 비율로 증가하고 있다면 2n이든, 5n이든, 10n이든 전부 O(n) 로 표기

💡 O(n²)

function printAllPairs(n) {
  for (var i = 0; i < n; i++) {  // O(n)
    for (var j = 0; j < n; j++) {  // O(n)
      console.log(i, j)
    }
  }
}

O(n) 연산 안에 O(n) 연산
= O(n * n)
= O(n²)

n이 커질 수록 실행 시간이 n 제곱의 값으로 증가하므로 O(n²)으로 표기한다.

📌 빅오 표현식 단순화 하기

이 모든 연산들을 다 세는 것은 힘들고, 사실 정확한 갯수가 중요하지 않다는 것을 알 수 있다.
중요한 것은 전체적인 추세!

5n + 2   ===>   O(n)

10n이든 1000n이든 중요하지 않음
추세 즉, 실행 시간이 n의 값과 비례한다는 것이 중요하다.

  O(2n)   ===>   O(n)
O(500)   ===>   O(1)
O(13n²)   ===>   O(n²)

대략적으로 정확한 큰 그림을 봐야 하므로, 상수는 신경쓰지 않는다.

O(n² + 5n + 8)   ===>   O(n²)

❗️ 추세를 나타낸 그래프를 아주 먼 우주에서 바라보고 있다고 생각하자.
작고 사소한 것에 신경쓰지 말고 큰 것에 집중해야 한다.

이 때, n제곱에 비해서 5n + 8은 아무 의미가 없다.

이렇게 상수를 없애고 나면, 단순화된 표현식들끼리 비교할 수 있다.

💡 빅오 표현식을 단순화하는 데에 도움을 주는 규칙들

1️⃣ 산술 연산은 상수다. (= 항상 일정한 값을 취한다.)
(덧셈, 뺄셈, 곱셈, 나눗셈을 포함)

컴퓨터에게는 2+2를 처리하는 시간과 1000000+2를 처리하는 시간이 비슷하다.
그러므로 n의 값이 상관이 없는 것 !

2️⃣ 변수에 값을 할당하는 것은 상수다.

3️⃣ 인덱스를 사용해 배열에 접근하거나, 키를 사용해 객체에 접근하는 것 또한 상수다.

4️⃣ 반복문이 있는 경우, 복잡도 = 루프의 길이 * 루프 안에 있는 연산들
0에서 n까지 반복한다면, n이 커질 수록 반복 횟수가 증가
이중 반복문이 있다면, 실행 시간은 n²

✨ 예시 3

function logAtLeast5(n) {
  for (var i = 1; i <= Math.max(5, n); i++) {
    console.log(i);
  }
}

n이 5보다 작다면 5번 반복하고, n이 5보다 크다면 n번 반복하는 함수
n이 커질수록 연산 개수가 n에 비례하여 증가하기 때문에 O(n)

✨ 예시 4

function logAtMost5(n) {
  for (var i = 1; i <= Math.min(5, n); i++) {
    console.log(i);
  }
}

n이 5보다 작다면 n번 반복하고, n이 5보다 크다면 5번 반복하는 함수
n이 커져도 아무런 영향을 주지 않기 때문에 O(1)

---

📌 공간 복잡도

입력이 커질수록 알고리즘이 얼마나 많은 공간(메모리)을 차지하는 지
입력되는 것을 제외하고 알고리즘 자체가 필요로 하는 공간

• boolean, number, undefined, null 타입은 모두 불변 공간
  입력의 크기와는 상관 없이 숫자가 1이든 1000이든 모두 불변 공간으로 여긴다.

• string 타입은 O(n) 공간이 필요
  만약 50자인 문자열이 있다면, 길이가 1자인 문자열보다 50배 더 많은 공간을 차지

• array, object 타입은 O(n) 공간이 필요
  만약 길이가 4인 배열이 있다면, 길이가 2인 배열보다 2배 더 많은 공간을 차지

예시

function sum(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total += arr[i]
  }
  return total
}

공간을 차지하는 부분
let total = 0
let i = 0

total += arr[i]
새로운 변수를 만드는 것이 아닌, 이미 선언된 변수에 더하는 것
=> 공간은 이미 할당되어 있고, 시간이 더 소요됨

상수 공간이 있는 코드 ===> O(1) 공간
(입력의 크기와는 상관없이 항상 똑같은 공간을 차지)

function double(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    newArr.push(2 * arr[i]);
  }
  return newArr;
}

각 배열의 요소가 두 배가 된 배열을 리턴하는 함수

입력된 배열의 길이가 10이라면, 새로운 배열에 저장되는 요소가 10개
=> 차지하는 공간은 입력된 배열의 크기와 비례하여 커지게 된다.

O(n) 공간을 차지하는 코드

O(log n)

log2(8) = 3 === 2³ = 8
: 2의 몇승의 값이 8이 되나요?

어떤 이진 로그를 대략 계산하기 위해서는 그 숫자가 1보다 작아지기 전에 2로 나눠지는 횟수를 알아내야 한다.

8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
log(8) = 3

25는 정확하게 2로 나눌 수 없음
25 / 2 = 12.5
12.5 / 2 = 6.25
6.25 / 2 = 3.125
3.125 / 2 = 1.5625
1.5625 / 2 = 0.78125
log(25) ≈ 4.64

<log와 관련있는 알고리즘>
탐색 알고리즘, 효율적인 정렬 알고리즘, 재귀
재귀는 시간이 아닌, 공간 복잡도와 관련

총 정리

• 알고리즘의 성능을 분석하기 위해서는 빅오표기법을 사용한다.
  입력의 크기, 전체적인 추세와 관련됨
• 빅오를 통해 시간 복잡도, 공간 복잡도에 대한 이해를 높일 수 있다.
• 정확도가 아닌 전체적인 추세를 중요시 한다.
• 빅오로 측정되는 알고리즘의 시간과 공간 복잡도는 하드웨어에 영향을 받지 않는다.
  (빅오는 실행될 연산의 갯수를 따지기 때문)

객체는 언제 사용할까?

• 정렬되어 있을 필요가 없을 때
• 빠른 접근, 입력, 제거를 원할 때

배열은 언제 사용할까?

• 정렬되어 있는 데이터가 필요할 때
• 빠른 접근, 입력, 삭제를 원할 때

객체의 빅오

입력 : O(1)
제거 : O(1)
탐색 : O(n) (어떤 특정한 정보가 어떤 값에 있는 지 확인하는 것)
접근 : O(1)

객체 메소드의 빅오

메소드	빅오
Object.keys	O(n)
Object.values	O(n)
Object.entries	O(n)
hasOwnProperty	O(1)

배열의 빅오

입력 : it depends
제거 : it depends
탐색 : O(n)
접근 : O(1)
❗️ 접근
JS에서 10000개의 요소가 있는 배열에서 9000번째 요소를 요청한다 가정했을 때, 0번째부터 9000번째까지 모든 엘리먼트를 하나씩 지나가는 것이 아님! 해당 인덱스로 바로 접근 가능하기 때문에 배열의 길이는 중요하지 않음
❗️ 입력
가장 끝에 추가하는 경우: O(1)
가장 앞에 추가하는 경우: O(n)
인덱스들이 1개씩 밀리기 때문에 엘리먼트마다 인덱스를 새로 배정하는 작업이 필요함
❗️ 제거
가장 끝에 있는 요소를 제거하는 경우: O(1)
가장 앞에 있는 요소를 제거하는 경우: O(n)
인덱스들이 앞으로 1개씩 당겨져야 하기 때문에 엘리먼트마다 인덱스를 새로 배정하는 작업이 필요함

효율적인 측면에서 봤을 때, 앞에서 추가/제거하는 것보다 끝에서 추가/제거하는 것이 더 효율적이다.
그러므로 효율을 생각한다면, 배열 앞에 데이터를 추가/제거하는 것은 최대한 피하는 것이 좋다.

배열 메소드의 빅오

메소드	빅오
push	O(1)
pop	O(1)
shift	O(n)
unshift	O(n)
concat	O(n)
slice	O(n)
splice	O(n)
sort	O(n * log n)
forEach/map/filter/reduce/etc.	O(n)

slice : 걸리는 시간은 복사하는 엘리먼트 개수만큼 증가