Algorithm 01. 빅오표기법

computer board

자바스크립트 알고리즘 빅오표기법.

서적 : ‘자바스크립트로 하는 자료 구조와 알고리즘’을 읽고 이해한 내용 정리

Algorithm Study(빅오 표기법) - 01. 😃

01. 빅오 표기법의 기초

  • O(1)\mathcal{O}(1) : 상수 시간.
  • O(n)\mathcal{O}(n) : 선형(Linear) 시간.
  • O(n2)\mathcal{O}(n^2) : 2차 시간.
  • O(logn)\mathcal{O}(log{}n) : 로그 시간.

02. 빅오 표기법의 규칙

알고리즘의 시간 복잡도를 f(n)\mathcal{f}(n)으로 표현한다고 가정.
여기서 nn은 입력의 개수.
f(n)\mathcal{f}(n)의 값은 소요 시간과 소요 공간(메모리)을 의미.

  1. 계수 법칙
    상수 kk00보다 클 때, f(n)\mathcal{f}(n)O(g(n))\mathcal{O}(g(n))이면, kf(n)\mathcal{kf}(n)O(g(n))\mathcal{O}(g(n))이다.
  2. 합의 법칙
    f(n)\mathcal{f}(n)O(h(n))\mathcal{O}(h(n))이고 g(n)\mathcal{g}(n)O(p(n))\mathcal{O}(p(n))이면 f(n)+g(n)\mathcal{f}(n) + \mathcal{g}(n)
    O(h(n)+p(n))\mathcal{O}(h(n) + p(n))이다.
  3. 곱의 법칙
    f(n)\mathcal{f}(n)O(h(n))\mathcal{O}(h(n))이고 g(n)\mathcal{g}(n)O(p(n))\mathcal{O}(p(n))이면 f(n)g(n)\mathcal{f}(n) * \mathcal{g}(n)
    O(h(n)p(n))\mathcal{O}(h(n)p(n))이다.
  4. 다항 법칙
    f(n)\mathcal{f}(n)kk차 다항식이면 f(n)\mathcal{f}(n)O(nk)\mathcal{O}(n^k)이다.

02-01. 계수 법칙 - 상수를 제거하라


입력(nn) 크기와 연관되지 않은 상수는 전부 무시하면 된다.

상수 k>0k > 0인 경우, f(n)\mathcal{f}(n)O(g(n))\mathcal{O}(g(n))이면, kf(n)\mathcal{kf}(n)O(g(n))\mathcal{O}(g(n))이다.

예를 들어 3f(n)3\mathcal{f}(n)f(n)\mathcal{f}(n)는 모두 동일한 O(g(n))\mathcal{O}(g(n))인 빅오 표기법을 가지게 된다.

Javascript로 해당 예시를 구현해보자.

// 3f(n)의 예시const fn3 = num => {
  let count = 0;
  for (let i = 0; i < num * 3; i++) {
    count += 1;
  }
  return count;
};

상단 코드는 3f(n)=3n3\mathcal{f}(n)=3n이다.

// f(n)의 예시const fn = num => {
  let count = 0;
  for (let i = 0; i < num; i++) {
    count += 1;
  }
  return count;
};

다음 코드는 f(n)=n\mathcal{f}(n)=n이다.

이때 상수 kk(여기서는 상수 k=3)는 코드 실행 횟수(nn)에 영향을 주지 않는다.
그러므로 상숫값이 무시되어 kf(n)\mathcal{kf}(n)O(g(n))\mathcal{O}(g(n))는 서로 동일하게 된다.

02-02. 합의 법칙 - 빅오를 더하라


합의 법칙은 서로 다른 시간 복잡도를 더할 수 있다는 것이다.

f(n)\mathcal{f}(n)O(h(n))\mathcal{O}(h(n))이고 g(n)\mathcal{g}(n)O(p(n))\mathcal{O}(p(n))이면 f(n)+g(n)\mathcal{f}(n) + \mathcal{g}(n)
O(h(n)+p(n))\mathcal{O}(h(n) + p(n))이다.

Javascript로 해당 예시를 보자.

// f(n)과 g(n)이 합해지는 예시const fnAddGn = num => {
  let count = 0;

  // f(n)
  for (let i = 0; i < num * 3; i++) {
    count += 1;
  }

  // g(n)
  for (let i = 0; i < num * 6; i++) {
    count += 1;
  }
  return count;
};

다음 함수fnAddGn의 경우, f(n)=3nf(n)=3ng(n)=6ng(n)=6n 두 가지가 실행되어 9n이 된다.
하지만 계수의 법칙을 적용하면 O(n)=n\mathcal{O}(n)=n이 된다.

이때 상수 kk(여기서는 상수 k=3)는 코드 실행 횟수(nn)에 영향을 주지 않는다.
그러므로 상숫값이 무시되어 kf(n)\mathcal{kf}(n)O(g(n))\mathcal{O}(g(n))는 서로 동일하게 된다.

02-03. 곱의 법칙 - 빅오를 곱하라


곱의 법칙은 빅오가 서로 곱해지는 것이다.

f(n)\mathcal{f}(n)O(h(n))\mathcal{O}(h(n))이고 g(n)\mathcal{g}(n)O(p(n))\mathcal{O}(p(n))이면 f(n)g(n)\mathcal{f}(n) * \mathcal{g}(n)
O(h(n)p(n))\mathcal{O}(h(n)p(n))이다.

역시 Javascript로 예시를 보자.

// 곱의 법칙 예시const multiplyFn = num => {
  let count = 0;

  for (let i = 0; i < num * 3; i++) {
    count += 1;

    for (let i = 0; i < num * 6; i++) {
      count += 1;
    }
  }

  return count;
};

다음 함수multiplyFn의 경우, f(n)=3n6nf(n)=3n*6n이 된다.
그러므로 연산 결과는 18n218n^2이다.
여기서 계수의 법칙을 이용하면 결과는 O(n)=n2\mathcal{O}(n)=n^2가 된다.

02-04. 다항 법칙 - 빅오의 kk


다항 법칙은 다항 시간 복잡도가 같은 다항 차수를 지닌 빅오 표기법을 지닌다는 뜻이다.

f(n)\mathcal{f}(n)kk차 다항식이면 f(n)\mathcal{f}(n)O(nk)\mathcal{O}(n^k)이다.

Javascript로 예시를 보자.

// 곱의 법칙 예시const multiplyFn = num => {
  let count = 0;

  for (let i = 0; i < num * num * num; i++) {
    count += 1;
  }

  return count;
};

다음 함수multiplyFn의 경우, f(n)=n3f(n)=n^3이 된다.
num * num * num회가 실행되기 때문이다.

02-05. 정리


빅오는 알고리즘의 효율을 분석하는 데 중요하다.

각 코드를 분석하여 빅오 표기법으로 단순화하기 위해 상단의 법칙들을 잘 적용하자.

👋


Written by@davidyang2149 (About me)
Hello World! This is David Yang Dev Blogs.

GitHub