Big O Notation (빅오 표기법)

Big O Notation is a way to formalize fuzzy counting.
대략적으로 숫자를 세는 것에 붙인 공식적인 표현이다.

It allows us to talk formally about how the runtime of an algorithm grows as the inputs grow.
정식으로 입력된 내용이 늘어날 수록 알고리즘에 실행 시간이 어떻게 변하는지 설명하는 공식적인 표현 방식이다.

빅오는 어떤 펑션(function)의 입력 값이 늘어나는 것과 펑션 실행 시간이 변하는 관계를 의미한다.
(입력의 크기와 실행시간의 관계)

The Problem with Time (코드를 비교할 때 시간을 비교하는 것의 문제)

  • Different machines will record different times
    기기마다 다른 방식으로 시간이 기록될 수 있다.
    차이가 달라질 수 있고 책정된 시간들이 달라질 수 있다.
  • The same machine will record different times
    같은 기기는 다른 시간을 기록할 수 있다.
    그렇기 때문에 기록된 시간을 완전하게 믿을 수 없다.
  • For fast algorithms, speed measurements may not be precise enough?
    빠른 알고리즘에는 짧은 시간안에 모든 것이 처리된다.
    이런 경우에는 속도 측정 정확도가 충분하지 않을 수 있다.

이러한 시간 문제점을 해결하는 코드를 비교하는 특정한 값이 빅오 표기법이다.

If not time, then what? (시간 대신 비교할 것은?)
Rather than counting seconds, which are so varable,
Let’s count the number of simple operations the computer has to perform.
코드 실행시간을 정확하게 초로 측정하는 것보다 컴퓨터가 처리해야하는 연산 갯수를 세면 된다.
어떤 컴퓨터를 사용하든 그 갯수는 변하지 않기 때문이다.

📁 Counting Operations (연산 갯수 세기)

  • 3 simple operations, regardless of the size of n 
    1
2
3
4

    function addUpTo(n) {
  // 1 multiplication, 1 addition, 1 division 
  return n * (n + 1) / 2;
}

    $O(1)$ : Always 3 operations

  • as low as 2n or as high as 5n + 2 
    1
2
3
4
5
6
7

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

    $O(n)$ : Number of operations is (eventually) bound by a multiple of n (say, 10n)
    연산의 갯수는 궁극적으로 N의 곱과 연결 되어있다.

Example 연산 갯수 📝

  • $O(n)$ countUpAndDown(n) 
    1
2
3
4
5
6
7
8
9
10
11
12
13

    function countUpAndDown(n) {
  console.log("Going UP!");
  //O(n)
  for (let i = 0; i < n; i++) {
      console.log(i);
  }
  console.log("At the top!\nGoing down...");
  //O(n)
  for (let j = n-1; j >= 0; j--) {
      console.log(j);
  }
  console.log("Back down. Bye!");
}

    $O(n)$ 이 두 개 존재한다. 이를 O(2n)이라고 착각할 수 있다.

    But regardless of the exact number,
    the number of operations grows roughly proportionally with n.
    사실 정확한 숫지는보다 중요한 것은 전체적인 추세를 보는 것이다.
    작업 수는 n이 커질수록 연산의 갯수로 비례적으로 늘어난다는 것이다.
    (그래프에 선이 n의 값과 비례)

  • $O(n^2)$ printAllParirs(n)의 중첩루프 
    1
2
3
4
5
6
7
8
9

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

    O(n) operation inside of an O(n) operation.
    n이 늘어날수록 연산들이 n값만큼 늘어난다.
    하지만 중첩루프로 안에 있는 연산들 또한 n값만큼 늘어날 것이다.

    $O(n*n)$
    n이 커질수록 실행 시간이 n제곱의 값으로 늘어난다.

📁 Big O Definition (빅오 정의)

  • f(n) could be linear $(f(n) = n)$
    입력과 실행 시간의 관계를 뜻하며 선형일 수 있다.
    즉 N의 값이 커질수록 실행 시간도 같이 늘어난다.
  • f(n) could be quadratic $(f(n) = n^2)$
    실행 시간이 N의 제곱일 수 있다.
  • f(n) could be constant $(f(n) = 1)$
    N이 커져도 실행 시간에는 아무런 영향을 받지 않기 때문에 항상 상수가 된다.
    단순하게 1로 표현한다.
  • f(n) could be something entirely different. 아니면 완전히 다를 수 있다.

📁 Simplifying Big O Expressions (빅오 표기법 단순화)

When determining the time complexity of an algorithm,
there are some helpful rule of thumbs for big O expressions.
위의 식들을 단순화하기 위해서 도움이 될 몇 가지 규칙들이 있다.

These rules of thumb are consequences of the definition of big O notation.
쉽게 따를 수 있는 규칙들은 경험에 바탕을 둔 방법이다.
가장 중요하게 생각하는 것은 대략적으로 정확한 큰 그림이다.

Constants Don’t Matter (상수는 중요하지 않다)

  • $O(2n)$ → $O(n)$
  • $O(500)$ → $O(1)$
  • $O(15n^2)$ → $O(n^2)$

Smaller Terms Don’t Matter (작은 연산은 중요하지 않다)

  • $O(n+17)$ → $O(n)$
  • $O(100n+7)$ → $O(n)$
  • $O(n^2+7n+11)$ → $O(n^2)$

Big O Shorthands (빅오 단순화 법칙)

  • Analyzing complexity with big O can get complicated
    빅오의 복잡도는 분석할 때 매우 복잡해진다.
  • There are several rules of thumb that can help
    섬세하게 작은 내용까지 따질 수도 있겠지만
  • These rules won’t ALWAYS work, but are a helpful starting point
    쉽게 적용할 수 있는 규칙이 있다. 항상 맞지는 않지만 좋은 시발점이 된다.
  1. Arithmetic operations are constant
    첫 번재, 산수는 상수이다. (덧셈, 뺄셈, 나눗셈을 포함)
    모든 상수 시간에 포함된다. n의 값이 상관 없다.
  2. Variable assignment is constant
    두 번째, 변수 배정도 상수이다.
    컴퓨터가 변수에 값을 배정하는데 걸리는 시간은 비슷하다.
  3. Accessing elements in an array (by index) or object (by key) is constant
    세 번째, 인덱스를 사용해서 배열 엘리먼트를 접근하거나
    배열에서 몇 번째 아이템을 찾던지 인덱스를 사용하면 똑같은 시간이 걸린다.
    또는 객체를 다루고 있는 데이터를 접근하기 위해서 키가 있다면
    그것도 실행 시간이 상수이다.
  4. In a loop, the the complexity is the length of the loop times the complexity of whatever happens inside of the loop
    네 번째, 루프가 있으면 복잡도 = 루프의 길이 * 루프 안에 있는 연산들 이 된다.
    그렇기 때문에 리스트 안에 있는 데이터를 루프로 처리할 때
    O에서 n까지 간다면, n이 커질수록 루프가 반복되는 횟수가 늘어난다.
    그렇다면 루프안에서 일어나는 작업들도 중요할 수 있다.
    만약 중첩 루프가 있다면 n제곱 실행 시간이 될 수 있다.

Example $O(n)$ 📝

1
2
3
4
5

function logAtLeast5(n) {
    for (var i = 1; i <= Math.max(5, n); i++) {
        console.log(i);
    }
}
logAtLeast5(1) 실행결과
1
2
3
4
5
logAtLeast5(7) 실행결과
1
2
3
4
5
6
7

logAtLeast5(n) 함수는 n까지의 숫자를 출력하지만, 최소한 1,2,3,4,5까지 출력한다.
n 이 무한대 까지 커지는 경우의 실행 시간을 예측한다면?
n이 100만이면 해당 루프는 100만번 반복되고 5는 중요하지 않게 된다.

위 함수의 Big O를 $O(n)$ 이라 말할 수 있다.
n이 커질수록 연산 갯수가 n에 비례해서 늘어나기 때문이다.

Example $O(1)$ 📝

1
2
3
4
5

function logAtMost5(n) {
    for (var i = 1; i <= Math.min(5, n); i++) {
        console.log(i);
    }
}
logAtMost5(30) 실행결과
1
2
3
4
5
logAtMost5(3) 실행결과
1
2
3

logAtMost5(n) 함수는 5보다 크면 무조건 MIN 더 작은 5를 선택한다.
또한 양수만 되며 0을 입력하면 아무것도 나오지 않는다.
5보다 작은 숫자를 입력하면 그 숫자만큼 출력된다.

중요한 것은 n이 커져도 아무 영향을 주지 않는 것이다.
n 이 100이든, 1000이든 더 작은 5만 선택하여 루프가 5번만 반복된다.
그렇기 때문에 n이 커질수록 Big O는 상수 $O(1)$라고 단순화할 수 있다.

$O(1)$과 $O(n)$ 그래프 📈

Big O graph
$O(1)$은 일직선으로 실행 시간이 $O(n)$ 보다 좋다고 표현할 수 있다.

Example 빅오 표현식, 시간 복잡도 📝

💡 빅오 표현식을 간단히 표기

  • $O(n+10)$ → $O(n)$
  • $O(100*n)$ → $O(n)$
  • $O(25)$ → $O(1)$
  • $O(n^2 + n^3)$ → $O(n^3)$
  • $O(n+n+n+n)$ → $O(n)$

💡 아래 함수에 대한 시간 복잡도를 구하기

1
2
3
4
5

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

답 : $O(n)$

1
2
3
4
5

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

답 : $O(1)$

1
2
3
4
5

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

답 : $O(n)$

1
2
3
4
5
6
7
8
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)$

1
2
3
4
5
6
7
8
9
10
11

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)$

🌞 정보 : 공부 기록용 블로그입니다. 오타나 내용 오류가 있을 경우 알려주시면 감사하겠습니다.

댓글남기기

Recent posts