Data-Structures

191017_TIL(Big-O)

Data-Structures

빅오 표기법

빅오 표기법 기초

빅오(Big-O) 표기법 시간 및 알고리즘 공간 복잡도 분석을 위해 등장하였다.

빅오(Big-O) 표기법을 배우면 시간(실행 시간)과 공간(사용된 메모리)관점에서 알고리즘 구현을 분석하는 법을 이해할 수 있다.

빅오 표기법에서 n은 입력의 개수를 나타낸다.

  • O(1) : 상수 시간
    • 예) 배열에 있는 항목을 인덱스를 사용해 접근하는 경우
  • O(n) : 선형 시간
    • 예) 0부터 n-1까지의 숫자를 출력하는 경우
  • O(n ^ 2): 2차 시간
    • 예) 이중 for문에서 각각 n-1까지 숫자를 출력하는 경우
  • O(log2n): 로그 시간
    • 예) 2의 1승부터 n승까지의 항목들을 출력하는 경우

빅오 표기법 규칙

  • 계수 법칙

    • 상수를 제거하라!

    • 빅오 표기법의 법칙 중 가장 중요하다.

    • 예)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      // f(n) = n인 코드 따라서 시간 복잡도는 O(n)
      function counter (n) {
          let count =0;
          for( let i = 0; i < n; i++) {
              count += 1;
          }
          return count;
      }

      // f(n) = 5n인 코드 계수 법칙에 따라 상수를 버리므로 시간 복잡도는 O(n)
      function counter (n) {
          let count =0;
          for( let i = 0; i < 5*n; i++) {
              count += 1;
          }
          return count;
      }

  • 합의 법칙

    • 빅오를 더하라!

    • 상위 알고리즘의 빅오 표기법은 단순히 해당 상위 알고리즘에 포함되는 두 개의 알고리즘의 합이다.

    • 합의 법칙을 적용한 다음 계수 법칙을 적용해야 한다는 점에 주의해야 한다.

    • 예)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      // 첫번째 for문은 f(n)=n, 두번째 for문은 f(n)=10n이고, 결괏값은 11n이다.
      // 계수 법칙을 적용하면 시간복잡도는 O(n)이 된다.
      function foo(n) {
          let count = 0;
          for (let i = 0; i < n; i++) {
              count += 1;
          }
          for (let i = 0; i < 10*n; i++) {
              count += 1;
          }
          return count;
      }

  • 곱의 법칙

    • 빅오를 곱하라!

    • 중첩 for 루프에 곱의 법칙이 적용된다.

    • 예)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      // f(n) = 10n * n, 즉, 10n^2이다. 계수 법칙을 적용하면 시간복잡도는 O(n^2)이다.
      function foo(n) {
          let count = 0;
          for (let i = 0; i < n; i++) {
              count += 1;
              for (let j = 0; j < 10*n; j++) {
              	count += 1;
          	}
          }
          return count;
      }

  • 다항 법칩

    • 빅오의 k승!
    • f(n)이 k차 다항식이면 f(n)은 O(n^k) 이다.

연습 문제

1
2
3
4
5
6
7
8
// 다음 코드의 시간 복잡도를 계산하라.
function foo(n) {
    
    for(let i = 0; i < n; i*2) {
        console.log(n);
    }
    
}

답. O(log2n) 로그복잡도다. 주어진 n에 대해 log2n번만 실행된다.

Share