Big O표기법과 little o표기법에 대한 설명

---

Big O표기법과 little o표기법에 대한 알아보도록 합시다.
이게 함수를 비교할 때 사용이 되는데요.

먼저, Big O 표기법은... 아래와 같습니다.

위를 'f(x)라는 함수는 g(x)의 Big O이다'라고 하죠.

개념적으로는, f(x)의 절대값이 x가 ∞로 감에 따라 언젠가는 
g(x)의 절대값에 임의의 양의 상수를 곱한 값보다 작아진다는 겁니다.


이를 아래와 같이 표현할 수 있습니다.

위에서 개념적으로 '언젠가는'이라고 말했는데,
그걸 어떤 x₀이라는 위치가 존재한다는 것을 수식으로 적어준 것이고요.

M은 양의 상수로써, 이런 양의 상수가 하나만 존재해도 Big O notation은 성립합니다.

예를 들어, 아래의 Big O 표기법은 성립합니다.

3x는 x²의 Big O입니다.
아래의 그래프를 보시면 명확해지죠.

x가 커짐에 따라서 이 두 함수의 차이는 점점 커져서,
3정도부터 이후에는  x²를 3x보다 크게 만드는 양의 상수곱을 쉽게 찾을 수 있습니다.

이 개념이 Big O입니다.

지금까지 Big O에 대해서는 x가 무한대를 향해 커지는 방향에 대해서만 언급했는데,
아래와 같이 특정값인 x_k에 가까워질 때에 대해서도 Big O의 개념을 적용할 수 있습니다.

더욱 자세한 사항은 위키백과를 참고해주세요.

---

이번에는 little o표기법에 대해서 알아보죠.
아래와 같이 적습니다.

앞서 Big O는 x가 무한대로 커질 때만 아니라 특정값에 가까워질때에 대해서도
사용될 수 있는 개념이라 했는데,

Little O는 x가 무한대로 커지는 상황에서만 사용되는 개념입니다
그리고 Big O보다 조건이 더욱 엄격합니다.

개념적으로 말하자면, 아래와 같습니다.

g(x)의 절대값에 어떤 작은 양의 숫자를 곱해도 f(x)보다는 크게되는 순간이 x를 키우다보면 
언젠가는 나타난다.

왜 조건이 더 엄격하냐면, '어떤 작은 양의 숫자를 곱해도'라는 조건이 추가되었기 때문입니다.
따라서, Little o를 성립하면 당연히 Big O도 성립하게 되죠.

Little o조건은 g(x)가 0이 아닐 때 아래와 동치인데, 아래의 조건이 좀 더 이해하기 쉬울 겁니다.

 

앞서 들었던 예를 다시 보면, 아래처럼 3x가 x²의 little o이기도 합니다.

아래의 그래프를 보면 이해가 빠를 것이예요.

위의 그래프에서 보이듯,
x가 증가함에 따라 x²에 0.5을 곱하든, 0.1을 곱해도... 훨씬 더 작은 수를 곱하더라도
3x보다는 커지게 되는 x를 반드시 찾을 수 있겠죠.

이건 x²의 증가율이 x보다 본질적으로 크기에 이런 것 입니다.

아무튼, 이럴 때 우리는 little o라고 합니다.