우선 앞에 설명한 개념인
Big O 와 little o의 차이점을 간단하게 설명하자면
O는 f(n)에 대해 >=를 만족하는 것을 표기한다면
o는 f(n)에 대해 >를 만족하는 것을 의미한다.
지난번 그래프를 다시한번 가져와서 비교해보자면
이 그래프의 선을 f(n)라 했을 때 O(n)은 그래프의 선부분에서 그 이하라고 했다면
o(n)은 저 선 미만의 영역을 의미한다.
즉 이하와 미만의 개념의 차이가 있다.
수학적으로 정의하자면
o(g(n)) = {f(n) | ∃n0 > 0 s.t. ∀c > 0 and n >= n0, f(n) < cg(n)}이다.
빅오의 표기법인
O(g(n)) = {f(n) | ∃ c > 0, n0 > 0 s.t. ∀ n > n0, f(n) <= cg(n)} 와 비교해서도 비슷하다.
다른점은 and로 ∀쪽에 조건이 붙었다는 것과 <=이 <로 바뀐 것이다.
이 역시도 구분해서 보자면
1. ∃ c > 0, n0 > 0
∃는 Exists란 의미로 존재한다는 뜻이다. 즉 0보다 큰 즉 양의 c와 n0가 존재 한다.
2. s.t. ∀c > 0 and n >= n0, f(n) < cg(n)
뒤의 조건이 만족하면 앞의 식이 만족된다는 의미이다.
3. ∀c > 0 and n >= n0
모든 양의 n과 c에 대해란 의미이다.
정리해보자면 모든 양의 n과 c가 f(n) < cg(n)을 만족한다면 양의 c와 n0가 존재한다는 의미이다.
위에서 말했듯이 그림에서 BigO가 선을 포함했다면 Little o는 선 미만의 지점들을 의미한다.
이 역시도 빅 오메가 표기법과 구분하면 이해하기 쉽다.
Ω는 f(n)에 대해 <=를 의미한다면
ω는 f(n)에 대해 <를 의미한다.
그래프의 선을 f(n)이라 했을 때 f(n)을 포함해서 이상인 영역이 Ω(n)라 한다면
그래프의 선 위의 영역이 ω(n)가 된다.
이상과 초과의 개념의 차이라 보면 된다.
수학적 표현으로 정의하자면
ω(g(n)) = { f(n) | ∃n0 > 0 s.t. ∀c > 0 and n >= n0, f(n) > cg(n)}
1. ∃n0 > 0
양의 n0가 있다.
2. s.t. ∀c > 0 and n >= n0, f(n) > cg(n)
뒤의 조건이 만족하면 앞의 식이 만족된다는 의미이다.
3. ∀c > 0 and n >= n0
모든 양의 n과 c에 대해란 의미이다.
즉 모든 양의 c와 n0보다 크거나 같은 n이 f(n) > cg(n)이다 란 의미이다.