Big O notation의 정의는 알고 쓰자

1. little O notation

 

두 함수  f(x)와 g(x)가 어떤 a에 대하여 

 

$$\left| f(x) \right| \leq \varepsilon g(x)$$

 

를 만족하는 모든 양의 상수 $\varepsilon $ 이

 

$0< \left| x-a \right| < \delta$에서 존재하게 하는 $\delta $가 존재한다면,

 

$$f(x) = o(g(x))$$  x →a 라고 표현한다.

 

 

동일한 말로 g(x)가 0이 아닐때, $$f(x) = o(g(x))$$ x →a 는

 

$$\displaystyle \lim_{ x \to a} \frac{f(x)}{g(x)} = 0$$과 동치이다.

 

근데 일단 이거는 그냥 극한으로 이해하는게 편한것 같다

 

 

2. 직관적인 이해

 

$$\displaystyle \lim_{ x \to a} \frac{f(x)}{g(x)} = 0$$으로부터 f(x)가 o(g(x))라는 것은 g(x)가 f(x)보다 빠르게 커진다는 이야기다.

 

하나 더 생각해보자면, 예를 들어 h →0 에서 f(h) = o(h)라고 한다면 정의에 의해

 

$\displaystyle \lim_{ x \to 0} \frac{f(h)}{h} = 0$인데, 이게 무슨말일까

 

 h →0에서 h가 f(h)보다 크다고 말할 수 있다.

 

h →0에서 h는 0에 가까워지는데 f(h)는 그것보다도 작다. 0이나 다름없다는 소리 그래서 little-O

 

 

3. 몇가지 성질

 

f = o(g)이고 g = o(h)이면 f = o(o(h)) = o(h)

 

f = o(g)이고 c가 0이 아닌 상수이면 cf = o(g)

 

x →a 에서 f(x) = o(x)이고 g(x) = o(x)이면 f+g = o(x)

 

f = o(F)이고 g = o(G)이면 fg = o(FG)

 

 

4. big O notation

 

두 함수 f,g에 대하여 x →a에서 f(x) = O(g(x))라는 것은

 

$0< \left| x-a \right| < \delta$을 만족하는 모든 x에 대해

 

$$\left| f(x) \right| \leq M g(x)$$를 만족시키는  양의 상수 $\delta$와 M이 존재한다는 것이다.

 

극한의 정의로 보면 

 

$$\displaystyle \lim sup_{ x \to a} \frac{\left|f(x) \right|}{g(x)} < \infty $$이다.

 

 

5. 프로그래밍에서의 이해

 

프로그래밍에서는 충분히 큰 입력데이터 n에 대해 알고리즘의 시간복잡도를 big O notation을 이용해서 표현한다

 

그러니까 

 

x →∞인 상황이다.

 

x →∞에서 f(x) = O(g(x))라고 표현한다는 것은 충분히 큰 모든 x에 대하여 f(x)의 절댓값이 g(x)의 양의 상수배 이하라는 것이다.

 

즉, $$\left| f(x) \right| \leq M g(x)$$을 만족시키는 양의 상수 M과 $x\geq x_{0}$을 만족시키는 충분히 큰 $x_{0}$가 존재한다.

 

컴퓨터과학에서는 조금 덜 제한적인 정의가 보편적으로 사용된다.

 

"정수 n에 대하여 f(n) = O(g(n))이라는 것은 $$\left| f(x) \right| \leq M g(x)$$이 $n\geq n_{0}$에 대한 모든 정수 n에서 성립하게 하는 충분히 큰 정수 $n_{0}$와 양의 정수 M이 존재한다는 뜻이다."

 

아무튼 극한으로 표현하자면 

 

$$\displaystyle \lim sup_{ x \to \infty } \frac{\left|f(x) \right|}{g(x)} < \infty$$인데

 

이건 limit superior이 와닿는 표현이 아니라서 말로 이해하는게 좋겠다

 

 

6. 주요 성질

 

6-1) f(x)가 몇가지 항의 합일때, 가장 큰 차수의 항을 제외하고는 나머지는 생략해도 좋다

 

6-2) f(x)가 어떤 요인들의 곱일때, 상수는 생략해도 좋다.

 

예를 들어 $f(x) = 6x^{4} - 2x^{3} + 5$이면 가장 큰 차수의 항을 제외하고 나머지는 생략하여 $f(x) = O(6x^{4})$

 

요인들의 곱일때, 상수는 생략할 수 있어서 $f(x) = O(x^{4})$

 

사실 이것은 정의에서 $$\left| f(x) \right| \leq M x^{4}$$을 만족하는 양의 상수 M과 $x\geq x_{0}$인 $x_{0}$가 존재한다는 뜻이다.

 

6-3) f1 = O(g1)이고 f2=O(g2)이면, f1 * f2 = O(g1 * g2)이고 f1 + f2 = O(max(g1,g2))

 

6-4) f*O(g) = O(fg)

 

 

7. 주요 사용처

 

컴퓨터 프로그래밍에서는 알고리즘의 시간복잡도를 계산하는데 사용하고

 

수학에서는 수식에 대한 근사식으로 주로 사용한다

 

$e^{x}$에 대한 근사식으로 1차항까지 근사시키고 싶을때, $1+x+O(x^{2})$으로 근사시키는 모습

 

 

 

Big O notation - Wikipedia

Big O notation - Wikipedia