시간복잡도의 점근적 표기법

 

알고리즘의 효율성은 주로 시간복잡도(time complexity)로 표기한다.

시간복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현한다.

시간복잡도를 표현하는 방법인 점근적 표기법과 최Big-O 표기법에 관해 간략하게 알아보자

 

점근적 표기법

입력 크기 n이 무한대로 커질때, 다른 어떤 함수로 근사되는지를 간단히 표현하기 위해 사용되는 표기법

 

점근적 상한

최악의 수행시간을 나타내기 위한 표기법이다.

주어진 알고리즘이 아무리 나빠도 비교하는 함수와 같거나 좋다.

 

점근적 하한

최선의 수행시간을 나타내기 위한 표기법이다.

 

점근적 상하한

복잡도의 상한과 하한이 동시에 적용되는 경우를 나타낸다.

 

Big-O notation

$ \mathrm{O}$ -표기는 복잡도의 점근적 상한을 나타낸다. 

 

어떤 양수  $n,  c $ 가 존재할 때,  $x \geq x_0$  이상의 모든  $ n$에 대해 $f(n) \leq cg(n)$  을 만족하면 $f(n) \fallingdotseq \mathrm{O}g(n) $

 

$c \cdot g(n)$은 $f(n)$의 상한이 되고, 알고리즘의 알고리즘 성능이 아무리 나빠도  $ cg(n)$ 보다 좋거나 같다

 

Big-O notation 표기 방법

함수의 최고차항이 대부분 Big-O가 된다.

 

[예시]

$f(n) = 10n^3 + 5n^2 + 20 $ =  $ \mathrm{O}(n^3) $

$f(n) = e^n + 10n^4 + 5n^3 + 20 $ =  $ \mathrm{O}(e^n) $   //지수 함수는 어떤 다항함수보다 빠르게 증가

$f(n) =500n log n + 300n $  =  $ \mathrm{O}(n log n) $ 

$f(n) =500 $  =  $ \mathrm{O}(1) $   //상수 함수는 $ \mathrm{O}(1) $ 로 나타낸다

 

Big - $ \mathrm{O}$ 표기 연산시간 크기 관계

 

상수  <  로그  <  선형  <  로그 선형  <   제곱  <  세제곱  <  지수

 Olog(1) < Olog(logn) < Olog(n) < O(nlogn) < O(n^2) < O(n^3) < O(e^n)

 

---

 

$\Omega$ notation

$\Omega$ 표기는 복잡도의 점근적 하한을 나타낸다

 

어떤 양수  $n,  c $ 가 존재할 때,  $x \geq x_0$  이상의 모든  $ n$에 대해 $f(n) \geq cg(n)$  을 만족하면 $f(n) \fallingdotseq \mathrm{O}g(n) $

 

$c \cdot g(n)$은 $f(n)$의 하한이 되고, 알고리즘 성능이 아무리 좋더라도 $f(n) $보다 좋아질 수 없다.

 

 

$\Omega$ 표기 방법

$\Omega$ 도 Big - $ \mathrm{O}$ 처럼 다항식의 최고차항만 계수 없이 취하면 된다.

 

[예시]

$f(n) = 10n^2 + 5n^3 + 20$  = $\Omega(n^2)$

 

n이 증가함에 따라 $f(n) = 10n^2 + 5n^3 + 20$ 이 $cn^2$ 보다 작을 수 없다는 의미이다.

 

 

 

 

 

 

 

 

 

 

 

[참고 문헌]

알기 쉬운 알고리즘 

 

[참고 사이트]

https://ledgku.tistory.com/31

https://neos518.tistory.com/37

https://hellowwworld.tistory.com/16

https://modoocode.com/246