알고리즘 수행시간 표기법

 

#1 알고리즘 수행시간

알고리즘 수행시간에 미치는 요소는 다양하지만,

일반적으로 '입력의 크기에 따른 컴퓨터의 기본 연산의 개수'로 단순화하여 알고리즘의 수행시간을 나타낸다.

 

 

 

#2 알고리즘 수행시간 표기법

[대표적인 알고리즘 수행시간 표기법]

① Big O

② Big Ω

③ Big Θ

 

일반적으로 Big O 표기법이 많이 사용된다.

 

 

 

 

 

#3 Big O 표기법

$ n : $ 입력크기

$ f(n) $, $ g(n) $ : 입력크기 n일 때의 알고리즘의 수행시간

(단, $ f(n) $, $ g(n) $은 양의 정수에서 양의 실수로의 함수)

 

$ f(n) \leq c \cdot g(n) $ $ \rightarrow{f = O(g)} $ (단, $ c > 0 $) 

 

[의미] 어떤 0보다 큰 상수 c에 대해 $ f(n) \leq c \cdot g(n) $이 만족하면, $ f = O(g) $라고 표기할 수 있다.

        엄밀하진 않지만 직관적으로 $ f = O(g) $은 $ f \leq g $를 의미한다.

 

 

 

 

 

 

#4 다른 표기법들의 의미

1. Big $ \Omega $

$ f = \Omega(g) $ 는 $ g = O(f) $을 의미한다.

즉, $ f = \Omega(g) $는 $ f \geq g $를 의미한다.

 

2. Big $ \Theta $

$ f = \Theta (g) $ 는 $ f = O(g) $ 이고 $ f = \Omega(g) $임을 의미한다.

즉, $ f = \Theta(g) $는 $ f = g $를 의미한다.

 

 

 

 

 

#4 단순화 규칙

Big O 표기법은 큰 그림에 집중할 수 있도록

몇 가지 일반적인 규칙들에 따라 무시할 수 있는 항들은 생략함으로써

단순화하여 알고리즘의 수행시간을 나타낸다.

 

1. 최고차항 외의 다른 항들은 무시한다.

ex. $ 5n^3 + 4n + 3 = O(n^3) $ 

 

2. 상수 배만큼 차이나는 함수들은 동일한 것으로 간주한다. 

(=상수 곱셈은 무시한다.)

ex. $ 2n + 20 = O(n) $

$ n + 1 = O(n) $

 

3.  $ a > b $ 이면 $ n^a $은 $ n^b $보다 빨리 증가한다.

ex. $ n^2 > n $

 

4. 임의의 지수함수는 다항함수보다 빨리 증가한다.

ex. $ 3^n > n^5 $

 

5. 임의의 다항함수는 로그보다 빨리 증가한다.

ex. $ n > (\log n)^3 $