[알고리즘 분석] 1장. 효율, 분석, 그리고 차수 (5)

1. 정확도(correctness) 분석

- 정확한 알고리즘 -> 어떠한 입력에 대해서도 답을 출력하면서 멈추는 알고리즘

- 정확하지 않는 알고리즘 -> 어떠한 입력에 대해서 멈추지 않거나, 틀린 답을 출력하는 알고리즘

 

2. 차수: 시간 복잡도 함수 ->$ \Theta (lg n)$, $ \Theta (n)$, $\Theta (n lg n) $등

 

3. 복잡도 함수 표기법

1) $ O() $ : big oh
- 점근적 상한(asymptotic upper bound)
- $ g(n) \in O(f(n)) $ 
- $ n \geq N$ 인 모든 정수 n에 대해서 $ 0 \leq g(n) \leq c\times f(n) $ 이 성립하는 양의 실수 c와 음이 아닌 정수 N이 존재한다.
- $ g(n) $은 $c\times f(n) $ 보다 절대로 더 느릴 수는 없다.

2) $ \Omega () $ : omega
- 점근적 하한(asymptotic lower bound)
- $ g(n) \in \Omega(f(n)) $
- $ n \geq N $인 모든 정수 n에 대해서 $ 0 \leq c\times f(n) \leq g(n) $ 이 성립하는 양의 실수 c와 음이 아닌 정수 N이 존재한다.
- $ g(n) $은 $c\times f(n) $ 보다 절대로 더 빠를 수는 없다. (아무리 빨라도 $ c\times f(n) $)

3) $ \Theta () $ : theta
- asymptotic tight bound
- $ g(n) \in \Theta(f(n)) $
- g(n)은 f(n)의 차수
- $ \Theta(f(n)) = O(f(n)) \cap \Omega (f(n)) $
- $ n \geq N $인 모든 정수 n에 대해서 $ c\times f(n) \leq g(n) \leq d\times f(n) $ 이 성립하는 양의 실수 c와 d, 음이 아닌 정수 N이 존재한다.

4) $ o() $ : small oh
- $ g(n) \in o(f(n)) $
- 모든 양의 실수 c에 대해, $ n \geq N $인 모든 n에 대해서 $ 0 \leq g(n) \leq c\times f(n) $이 성립하는 음이 아닌 정수 N이 존재한다.
- $ \lim_{n \to \infty }\frac{g(n)}{f(n)} = 0 $

5) $ \omega () $ : small omega
- $ g(n) \in \omega(f(n)) $
- 모든 양의 실수 c에 대해, $ n \geq N $인 모든 n에 대해서 $ 0 \leq c\times f(n) \leq  g(n) $이 성립하는 음이 아닌 정수 N이 존재한다.
- $ \lim_{n \to \infty }\frac{g(n)}{f(n)} = \infty$