[알고리즘 with JS] 빅 오 표기법(Big O Notation)이란?

빅 오 표기법(Big O Notation)에 대해 알아보겠습니다.

 

목차

 

 

우선, 문제 하나 풀고 가실까요?

 

💡 quiz. 1부터 특정한 N 값과 그 사이에 있는 모든 숫자들을 더하는 함수를 만들어보세요.

 

📌 해답 1

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

 

total이라는 값을 먼저 선언하고 인자로 받은 n의 값만큼 for문을 반복하면서 total에 값을 더하고 있습니다.

 

문제를 해결할 수 있으며, 가장 쉽게 ? 떠올릴 수 있는 방법입니다. 

 

이런 방법은 어떨까요 ? 

 

 

📌 해답 2

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

 

해답 1에 비해 엄청나게 간소화 된 식입니다. 하지만 마찬가지로 같은 결과를 출력할 수 있습니다.

 

해답 1과 해답 2가 같은 값을 출력해 낸다면 값을 출력하기 까지의 시간을 비교해보면 어떨까요?

 

 

해답 1은 대략 1.25초가 걸리고 해답 2는 대략 0.00001초가 걸리게 됩니다. 

 

이렇게 우리는 같은 문제를 가지고 어떤 해결 방식으로 접근하냐에 따라 다른 결과를 나타낼 수 있습니다.

 

성능을 비교하는 데 있어 가장 간단하게 접근할 수 있는데 시간이지만, 시간을 비교하는게 무조건 완벽한 방법은 아닙니다. 

 

[ 시간 싸움의 문제 ]

 

1. 컴퓨터의 성능에 따라 다른 시간을 기록할 수 있습니다. 

 

2. 같은 컴퓨터라도 다른 시간을 기록할 수도 있습니다. ( 매번 실행에 따른 결과가 다를 수 있음 )

 

3. 엄청나게 빠른 알고리즘의 경우 속도 측정히 충분히 정확하지 않을 수 있습니다. 

 

이런 이유 때문에 코드를 살펴 보면서 시간을 측정하지 않고, 어느 코드가 더 좋은 지 평가 할 수 있는 방법을 찾게 되었습니다. 

 

만약, 시간을 측정하는게 아니라 컴퓨터가 수행해야 할 연산의 갯수를 새는 방법은 어떨까요?

 

[ 빅 오 표기법 (Big O Notation) ]

빅오 표기법이란, 인자가 특정한 값이나 무한대로 향할 때 함수의 극한적인 동작을 설명하는 수학적인 표기법입니다.

 

O(n²)을 보며 빅오 표기법이 무엇인지 살펴보겠습니다. O(n²)은 빅 오 제곱이라고 읽습니다. 여기서 n은 입력값의 크기를 나타냅니다. 그리고 O()안에 있는 함수 f(n)은 입력값의 크기에 따라 얼마나 알고리즘이 복잡해지는지 알려줍니다. 

 

• f(n)은 선형일 수 있습니다. f(n) = n 
• f(n)은 2차 방정식일 수 있습니다. f(n) = n²
• f(n)은 상수일 수 있습니다. f(n) = 1
• f(n)은 그 외의 다른 것도 가능합니다.

 

[ 빅 오 표기법의 단순화 ]

알고리즘의 시간 복잡도를 결정할 때 Big O 표현에 대한 도움을 줄 수 있는 몇 가지 유용한 법칙이 있습니다. 이러한 법칙은 Big O 표기법 정의에 대한 결과를 나타냅니다. 

 

※ 상수는 중요하지 않습니다.  중요한 것은 대략적인 큰 그림입니다.

 

📌 1. O(2n) => O(n) 

앞의 상수는 중요하지 않습니다. 

 

📌  2. O(500) => O(1)

O(500)은 쉽게 말하면 연산 갯수가 어떤 상황에든 500개가 있다는 것입니다. 즉, 변동이 없습니다. 

 

📌  3. O(13n²) => O(n²)

13n²이 무진장 많이 커진다면, 정말 셀 수 없이 커진다면 앞에 있는 13이 큰 의미가 있을까요? n² 보다?? 

 

 

※ 더 작아지는 것도 중요하지 않습니다.

 

📌 1. O( n + 10 ) => O(n) 

 

📌 2. O( 1000n + 50 ) => O(n) 

 

📌 3. O( n² + 5n + 8 ) => O(n) 

 

※ Tip

 

1. 산수는 상수입니다.  ( 덧셈, 뺼셈, 곱셈, 나눗셈을 포합합니다. ) 

 

2. 변수 선언도 상수입니다. 컴퓨터가 변수에 값을 배정하는데 걸리는 시간은 비슷합니다.

 

3. 인덱스를 사용하여 배열 엘리먼트에 접근하는 것 역시 상수입니다.

 

4. 루프가 있다면 복잡도가 루프의 길이 곱하기 루프 안에 있는 연산이 됩니다. 만약 루프 내 중복이 있다면 n 제곱이 될 수 있습니다.

 

 

 

위로 갈수록 좋고, 아래로 갈수록 나쁩니다.

 

시간 복잡도	의미
O(1)	상수 시간 (constant time)
O(logN)	로그 시간 (log time)
O(N)	선형 시간 (linear time)
O(NlogN)	로그 선형 시간 (log-linear-time)
O( n^2)	이차 시간 (quadratic time)
O( n^3)	삼차 시간 (cubic time)
O( 2^n)	지수 시간 (exponential time)

 

🧷 아래 페이지에 들어가서 여러가지 테스트를 하면서 그래프의 증감을 확인해보세요

 

https://rithmschool.github.io/function-timer-demo/

Big O Introduction

⭐️ Quiz

1. 다음 빅오 표현식을 간단히 해보세요 - O(n + 10) 

 

정답: O(n)

 

2. 다음 빅오 표현식을 간단히 해보세요 - O(100+ n) 

 

정답: O(n)

 

3. 다음 빅오 표현식을 간단히 해보세요 - O(25) 

 

정답: O(1)

 

4. 다음 빅오 표현식을 간단히 해보세요 - O(n^2 + n^3) 

 

정답: O(n^3)

 

5. 다음 빅오 표현식을 간단히 해보세요 - O(n + n + n + n) 

 

정답: O(n)

 

6. 아래 함수에 대한 시간 복잡도를 구하세요. 

function logUpTo(n) {
    for (var i = 1; i <= n; i++) {
        console.log(i);
    }
}

 

정답: O(n)

 

7. 아래 함수에 대한 시간 복잡도를 구하세요. 

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

 

정답: O(1)

 

8. 아래 함수에 대한 시간 복잡도를 구하세요. 

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

 

정답: O(n)

 

9. 아래 함수에 대한 시간 복잡도를 구하세요. 

function onlyElementsAtEvenIndex(array) {
    var newArray = Array(Math.ceil(array.length / 2));
    for (var i = 0; i < array.length; i++) {
        if (i % 2 === 0) {
            newArray[i / 2] = array[i];
        }
    }
    return newArray;
}

 

정답: O(n)

 

10. 아래 함수에 대한 시간 복잡도를 구하세요. 

function subtotals(array) {
    var subtotalArray = Array(array.length);
    for (var i = 0; i < array.length; i++) {
        var subtotal = 0;
        for (var j = 0; j <= i; j++) {
            subtotal += array[j];
        }
        subtotalArray[i] = subtotal;
    }
    return subtotalArray;
}

 

정답: O(n^2)

 

 

 

[ 공간 복잡도 (Space Complexity) ]

지금까지 시간 복잡도에 초점을 맞추었습니다. 이제 입력 크기가 증가함에 따라 알고리즘의 실행 시간을 어떻게 분석할 수 있는지 알게 되었습니다.

 

또한, Big O 표기법을 사용하여 공간 복잡도를 분석할 수도 있습니다.

 

대충 이런 식입니다. 알고리즘에서 코드를 실행하기 위해 할당해야 하는 추가 메모리 양은 얼마입니까? 

 

때로는 입력이 차지하는 공간을 포함하지 않고 알고리즘에 필요한 공간을 참조하기 위해 공간 복잡도를 사용할 것입니다.

 

 

[ 공간 복잡도의 규칙 ]

1. 대부분의 Primitives (booleans, undefined, null)은 constant space(상수 공간) 입니다. 

 

2. String은 O(n)의 공간이 필요합니다. ( 여기서 n은 문자열의 길이입니다. ) 

 

3. Reference types들도 일반적으로 O(n)입니다. 배열의 경우 n은 길이를 나타내며 객체의 경우 n은 키의 수 (number of keys) 입니다. 

 

⭐️ Quiz 

1. 아래 함수에 대한 공간 복잡도를 구하세요. 

function logUpTo(n) {
    for (var i = 1; i <= n; i++) {
        console.log(i);
    }
}

 

정답: O(1)

 

2. 아래 함수에 대한 공간 복잡도를 구하세요. 

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

 

정답: O(1)

 

3. 아래 함수에 대한 공간 복잡도를 구하세요. 

function onlyElementsAtEvenIndex(array) {
    var newArray = Array(Math.ceil(array.length / 2));
    for (var i = 0; i < array.length; i++) {
        if (i % 2 === 0) {
            newArray[i / 2] = array[i];
        }
    }
    return newArray;
}

 

정답: O(n)

 

4. 아래 함수에 대한 공간 복잡도를 구하세요. 

function subtotals(array) {
    var subtotalArray = Array(array.length);
    for (var i = 0; i < array.length; i++) {
        var subtotal = 0;
        for (var j = 0; j <= i; j++) {
            subtotal += array[j];
        }
        subtotalArray[i] = subtotal;
    }
    return subtotalArray;
}

 

정답: O(n)