logo
Published on

알고리즘 : Big-O 표기법

Authors
  • avatar
    Name
    Bora Choi
    Twitter

빅오 표기법이 필요한 이유

코드의 성능을 평가하는 이유

  • 서로 다른 접근법간에 더 나은 접근법을 찾는데 유용합니다.
  • 코드 속도가 느려지거나 오류가 발생할때, 비효율적인 코드 부분을 식별하면 프로그램의 취약점을 찾는데 도움이 됩니다.

그렇다면 좋은 성능의 코드란 무엇일까?

속도가 빠른 코드? 메모리 점유도가 적은 코드? 가독성이 좋은 코드?

속도(시간 측정)로 평가하기

  • 같은 코드일지라도 컴퓨터 성능에 따라 다른 시간을 측정합니다.
  • 한 컴퓨터에서 한 코드를 실행할때 매번 같은 시간이 측정되는것은 아닙니다.
  • 엄청 빠른 알고리즘은 과연 정확하게 측정되었을까요?

그럼 시간이 아니라면 어떻게 코드 성능을 평가하는 것이 좋을까요 ?

→ 컴퓨터가 연산을 수행하는 횟수를 세어봅시다!

function N까지숫자의합(n) {
  let total = 0
  for (let i = 1; i <= n; i++) {
    total += i
  }
  return total
}

위 코드의 경우 총 5n+ 2번의 연산을 수행 하게 됩니다.

그러나 매번 연산횟수를 계산하는 것은 어려울 수 있습니다.

그래서 Big O 표기법을 사용합니다.

Big-O 표기법 기본 지침

Big-O 표기법은 알고리즘의 최악의 경우 복잡성을 측정합니다. 알고리즘을 구현할때 알고리즘이 얼마나 효율적인지 알려주기 때문에 Big-O 표기법은 중요합니다. Untitled

constant time O(1)

O(1)은 입력에 변경되지 않습니다. 따라서 O(1)은 일정한 시간(constant time)이라고 합니다.

O(1) 알고리즘의 예시로는 인덱스별로 배열의 항목에 참조하는 것입니다.

const arr = [1, 2, 3]
console.log(arr[0])

linear time O(n)

O(n)은 선형 시간(linear time)이며 최악의 경우에서 n번 작업을 수행해야하는 알고리즘에 적용됩니다.

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

quadratic time O(n^2)

function quadratic(n) {
  for (var i = 0; i < n; i++) {
    console.log(i)
    for (var j = 0; j < n; j++) {
      console.log(j)
    }
  }
}

cubic time O(n^3)

function cubic(n) {
  for (var i = 0; i < n; i++) {
    console.log(i)
    for (var j = 0; j < n; j++) {
      console.log(j)
      for (var k = 0; k < n; k++) {
        console.log(k)
      }
    }
  }
}

logarithmic time O(log n)

로그시간 복잡성의 효율성은 큰 입력이 주어졌을때 두드러집니다. 예를 들어 log2 (1000000)는 19.9315686 이기때문에 19번만 출력하면됩니다.

function logarithmic(n) {
  for (var i = 2; i <= n; i = i * 2) {
    console.log(i)
  }
}

Big-0 표기법의 규칙

알고리즘의 복잡성을 f(n)으로 표현한다면 n은 입력수를 나타내고, f(n)time 은 필요한 시간을 나타내며, f(n)space는 알고리즘에 필요한 공간(추가메모리)을 나타냅니다. 알고리즘 분석의 목표는 f(n)를 계산하여 알고리즘의 효율성을 이해하는 것입니다. 그러나 f(n)을 계산하는 것은 어려울 수 있습니다. Big-O표기법은 개발자가 f(n)을 계산하는 데 도움이 되는 몇 가지 기본 규칙을 제공합니다.

Coefficient rule : " Get Rid of Constants" 계수 규칙 : 상수 제거하기

f(n)= O(g(n)) 이면 k>0에 대해 kf(n)=O(g(n))입니다. 첫 번째 규칙은 입력 크기와 관련이 없는 계수를 제거하는 계수 규칙입니다. n이 무한대에 접근함에 다라 다른 계수는 무시할 수 있기 떄문입니다.

function a(n) {
  var count = 0
  for (var i = 0; i < 5 * n; i++) {
    count += 1
  }
  return count
}

Sum rule : "Add Big-Os Up" 합 규칙 : 빅오 더하기

f(n)=O(h(n))이고 g(n)=O(p(n))이면, f(n)+g(n) = O(h(n)+p(n))입니다. 합 규칙은 단순히 결과 시간복잡성이 두가지 다른 시간 복잡정의 합인경우 , 결과 Big-O 표기법도 두개의 다른 Big-O 표기법의 합계입니다.

Product rule : "Multiply Big-Os" 곱 규칙 : 빅오 곱하기

f(n)=O(h(n))이고 g(n)=O(p(n))이면, f(n)g(n) = O(h(n)p(n)) 입니다다.

Polynomial rule : " Big-O to the Power of k " : 다항식 규칙 : 빅오의 k승

f(n)이 k차 다항식이면 f(n)=O(n^k)입니다.

Discuss on Twitter • View on GitHub