[알고리즘 분석]7. Big-Oh Notation(빅 오 표기법)

목차

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

2. Big-Oh Examples(예시)

3. Big-Oh and Growth Rate

4. Big-Oh Rules(규칙들)

 

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

 Big-Oh Notation(빅 오 표기법)을 간단히 설명하면 다음과 같습니다. Input n에 대한 수행시간 함수를 f(n), g(n)이라고 할 시, 아래의 조건들을 만족하면 f(n)은 O(g(n))이라고 할 수 있습니다. 

 

1. f(n) <= cg(n) 이며 n >= n0 를 만족하는

2. 두 양의 상수 c와 n0가 존재할시

 

 위와 같은 설명으론 체감이 잘 안되므로, '2n+10이 O(n)이다'로 예시를 들어보면,

1. 2n+10 <= cn

2. (c-2)n >= 10

3. n <= 10/(c-2)

이를 만족하는 c = 3, n0 = 10이 존재하므로 성립한다!

 

2. Big-Oh Examples(예시)

1) 7n - 2

- 7n-2 는 O(n)이다.

- 7n-2 <= cn, n >= n0를 만족하는 c = 7, n0 = 1

 

2) 3n^3 + 20n^2 + 5

- 3n^3+20n^2+5 는 O(n^3)이다.

- 3n^3+20n^2+5 <= cn^3, n >= n0를 만족하는 c = 4, n0 = 21

 

3) 3logn + 5

- 3logn+5 는 O(logn)이다.

- 3logn+5 <= clogn, n >= n0를 만족하는 c = 8, n0 = 2

 

3. Big-Oh and Growth Rate

 Big-Oh Notation(빅 오 표기법)은 결국 특정 함수 growth rate의 upper bound(함수 증가율의 상한)을 의미한다. 즉, O(g(n))은 g(n)보다 증가율이 느리거나, 같은 함수들의 집합이 된다.

 

4. Big-Oh Rules(규칙들)

 위의 Big-Oh 정의와 예시들을 관찰해 보면, 공통적인 특징을 확인할 수 있습니다. 바로 f(n)이 d차항 다항식이라면, 이를 BIg-Oh로 표기할시 O(n^d)로 나타난다는 사실입니다. 따라서,

1. f(n)이 d차항 다항식이라면, O(n^d), clogn일 경우 O(logn)

2. 가능한 차수가 작고, 간단한 Big-Oh 사용하기

ex) 2n은 O(n^2)이기도 하지만, 더 간단한 O(n) 사용

ex) 3n+5는 O(3n)이기도 하지만, 더 간단한 O(n) 사용