빅-오 표기법(Big-Oh Notation)

ROK·2022년 9월 21일
0

열혈 자료구조

목록 보기
1/30

데이터 수(n)에 따른 시간 복잡도 함수(T(n))을 정확하게 구하는 것은 대부분 쉽지 않다.

시간복잡도 함수 T(n)은 근사치(approximation) 식을 구성해도 문제가 되지 않는다

시간복잡도 함수가 T(n)=n2+2n+1T(n) = n^2 + 2n + 1와 같다면 T(n)=n2+2nT(n) = n^2 + 2n로 간략화해도 된다.

그리고 더 나아가 T(n)=n2T(n) = n^2와 같이 간략화해도 문제가 없다

이는 수학적으로 봤을 때 2n2n은 뺏을 때 값에 많은 영향을 줄 것 같지만 그렇지 않다. 아래 표를 보면 알 수 있다.

nnn2n^22n2nT(n)T(n)n2n^2의 비율
101002012083.33%
10010,00020010,20098.04%
1,0001,000,0002,0001,002,00099.80%
10,000100,000,00020,000100,020,00099.98%
100,00010,000,000,000200,00010,000,200,00099.99%

위 표는 임의의 값 nn이 있을 때 n2n^2이 차지하는 비율을 나타낸다.
비율을 살펴보면 nn의 값이 커질수록 n2n^2이 차지하는 비율은 확실히 커지게 된다.

따라서 T(n)=n2+2n+1T(n) = n^2 + 2n + 1T(n)=n2T(n) = n^2로 표현할 수 있다.
그리고 위 함수를 빅-오 표기법으로 표현하면 O(n2)O(n^2)과 같이 표현할 수 있다.

그리고 이를 일반화하면 다음과 같다.
T(n)=amnm+am1nm1++alnl+a0O(nm)T(n) = a_mn^m + a_{m-1}n^{m-1} + \cdots + a_ln^l + a_0 \Rightarrow O(n^m)

즉, 다항식으로 표현된 시간 복잡도 함수 T(n)T(n)에서 큰 의미를 갖는 것은 '최고차항의 차수(nmn^m)'이다

이는 최고차항이 9999n29999n^2일때도 똑같이 n2n^2이 된다.

그럼 계수가 9999인 것은 꽤나 큰 의미를 가질텐데 왜 그럴까??
이는 다음과 같다
데이터의 수(n)가 5개일 경우 연산 횟수의 증가가 각각 52=255^2 = 25, 9999×52=2499759999 \times 5^2 = 249975로 둘의 차이가 크다.

하지만 빅-오의 관점에서는 다음과 같이 본다
데이터의 수가 2, 3, 4개로 늘어날 때 연산횟수는 4, 8, 16으로 두배씩 증가
데이터의 수가 2, 3, 4개로 늘어날 때 연산횟수는 99, 198, 396으로 두 배씩 증가

결론적으로 2배씩 증가하는 것은 같다.
이는 O(logn)O(log { n})으로 데이터 증가에 따른 연산횟수의 증가 형태를 좌표평면상에 그리면 증가하는 추세가 둔화되는 형태를 띈다. (로그 그래프와 유사한 형태를 그린다)

대표적인 빅-오

O(1)O(1)

  • 상수형 빅-오라고 한다.
  • 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘을 의미
  • 예를 들어 연산 횟수가 데이터 수에 상관없이 3회씩 진행되는 알고리즘이라도 O(3)O(3)가 아닌 O(1)O(1)이라고 한다.

O(logn)O(logn)

  • 로그형 빅-오라 한다.
  • '데이터 수의 증가율'에 비해 '연산횟수의 증가율'이 훨씬 낮은 알고리즘을 의미
  • 매우 바람직한 유형이다

O(n)O(n)

  • 선형 빅-오라 한다.
  • 데이터의 수와 연산횟수가 비례하는 알고리즘을 의미

O(nlogn)O(nlogn)

  • 선형로그형 빅-오라 한다.
  • 데이터의 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘을 의미
  • nnlognlogn을 곱한 형태로 난해해 보이지만, 이에 해당하는 알고리즘이 적지 않음

O(n2)O(n^2)

  • 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미
  • 데이터 양이 많은 경우 적용하기에 부적절
  • 일반적으로 이중 중첩된 반복문 내에서 알고리즘 연산이 이루어지기 때문에 발생
  • 중첩된 반복문의 사용은 알고리즘 디자인에서 그리 바람직하지 않다.

O(n3)O(n^3)

  • 데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미
  • 일반적으로 삼중 중첩된 반복문 내에서 알고리즘 연산이 이루어지기 때문에 발생
  • 이 또한 제곱과 같이 적용하기에는 무리가 있는 알고리즘이다.

O(2n)O(2^n)

  • 지수형 빅-오
  • 사용하기에 매우 무리가 있는, 사용하는 것 자체가 비현실적인 알고리즘
  • 매우 무서운 연산횟수의 증가
  • 만약 알고리즘이 이런 성능을 보이면, 개선의 과정을 거쳐 가장 현실적인 연산횟수를 보이는 알고리즘으로 수정되어야 한다.

빅-오의 성능 대소 정리

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

빅-오 그래프

아래는 대표적인 빅-오의 '데이터 수의 증가에 따른 연산횟수 증가율'을 그래프로 정리한 것이다.

profile
하루에 집중하자

0개의 댓글