Growth of Functions

Gorwth of Functions: 함수의 성장

함수의 행동을 한계에서 설명하는 방식을 asymptopic effciency(점근적 효율성)이라고 한다.

이 방식에서는 저차항과 상수계수를 무시하고 중요한 부분에 집중하여 알고리즘의 실행시간을 나타낸다.

알고리즘의 실행시간으로는 함수의 크기(알고리즘의 성능)를 비교할 수 있다.

---

빅세타, 빅오, 빅오메가

 

위 사진은 $\Theta, O, \Omega$ 표기법의 그래프 예시다.

각 부분에서, $n_0$의 값은 가능한 작은 값이며, 이보다 더 큰 값도 동일한 역할을 할 수 있다.

여기서 역할이란, f(n)과 g(n)을 비교하는 임의의 시작점이다.

 

(a) 빅세타(Big Θ) 표기법

양의 상수 $n_{0}, c_{1}, c{2}$가 존재하며, $n_0$의 오른쪽에서 $f(n)$의 값이 항상 $c_{1}g(n)$과 $c_{2}g(n)$사이에 포함된다면, 빅세타 표기법을 사용한다.

$$f(n) = \Theta(g(n))$$

 

(b) 빅오(Big O) 표기법

빅오 표기법은 함수에 대한 상한을 상수 계수 내에서 제공한다.

양의 상수$n_{0}, c$가 존재하며, $n_0$의 오른쪽에서 $f(n)$의 값이 항상 $cg(n)$보다 작거나 같다면, 빅오 표기법을 사용한다.

$$f(n) = O(g(n))$$

 

(c) 빅오메가(Big Ω) 표기법

빅오메가 표기법은 함수에 대한 하한을 상수 계수 내에서 제공한다.

양의 상수$n_{0}, c$가 존재하며, $n_0$의 오른쪽에서 $f(n)$의 값이 항상 $cg(n)$보다 크거나 같다면, 빅오메가 표기법을 사용한다.

$$f(n) = \Omega(g(n))$$

---

Asymptotic Notation: 점근적 표기법

O-notation

$O(g(n))$은 $f(n) \leq cn$일 때 성립된다.

위 식에서의 c의 값과 $n_0$ 값의 존재를 보이면 f(n)은 O(g(n))이라고 말할 수 있다.

 

$O(g(n))$ = {f(n): 모든 $n \geq n_0$에 대해서 $0 \leq f(n) \leq cg(n)$를 성립하는 양의 상수 c와 $n_0$이 존재한다.}

g(n)은 f(n)의 asymptotic upper bound(점근적 상계)이다.

 

예시를 들면,

$2n^2 = O(n^3)$이고, c=1 & $n_0 = 2$일 때 성립한다.

 $0 \leq f(n) \leq cg(n)$의 식에 대입해보자면, $0 \leq 2n^2 \leq 1・n^3$ 이고, n값에 2를 대입하면 성립하니, 증명이 된 것이다.

 

또한,

$2n^2 = O(n^2)$이고, c=2 & $n_0 = 0$일 때 성립한다.. 이 때, c는 실수여도 상관없다.

$0 \leq 2n^2 \leq 2・n^2$이고, n값에 0을 대입하면 식이 성립하니, 이 역시 증명이 되었다.

 

$O(n^2)$이 되는 다른 식에는,

$n^2$, $n^2 + 2$, $n$, $n/1000$, $n^{1.999}$ 등이 존재한다.

 

$\Omega$-notation

$\Omega(g(n))$은 $f(n) \geq cn$일 때 성립한다.

$\Omega(g(n))$ = {f(n): 모든 $n \geq n_0$에 대해서 $0 \leq cg(n) \leq f(n)$를 성립하는 양의 상수 c와 $n_0$이 존재한다.}

g(n)은 f(n)의 asympotic lower bound(점근적 하계)이다.

 

예시를 들면,

$\sqrt{n} = \Omega(lg n)$이고, c=1 & $n_0 = 16$일 때 성립한다.

$0 \leq 1・lg n \leq \sqrt{n}$이고, n의 값이 16을 대입하면 식이 성립한다.

 

$\Omega(n^2)$이 되는 다른 식에는,

$n^2$, $1000n^2 - 1000n$, $n^3$, $n^2 lg lg lg n$ 등이 존재한다.

 

$\Theta$-notation

$\Theta(g(n))$ = {f(n): 모든 $n \geq n_0$에 대해서 $0 \leq c_{1}g(n) \leq f(n) \leq c_{2}g(n)$를 성립하는 양의 상수 $c{1}, c{2}$와 $n_0$이 존재한다.}

g(n)은 f(n)의 asymptotic tight boud(점근적 근접선...?)이다. 즉, f(n)이 두 개의 g(n) 함수 사이에 껴있는 것이다.

 

예시를 들면,

$n^{2}/2 - 2n = \Theta(n^2)$이고, $c_1 = 1/4, c_2 = 1/2$와 $n_0 = 8$일 때 성립한다.

$0 \leq 1/4・n^2 \leq n^{2}/2 - 2n  \leq 1/2・n^2$이고, n값에 8을 대입하면 식이 성립한다.

 

정리하자면,

$f(n) = \Theta(g(n))$ iff $f = O(g(n))$ and $f = \Omega(g(n))$이다.

빅오 표기법의 $c_1, n_1$과 빅오메가 표기법의 $c_2, n_2$가 빅세타 표기법의 $c_1, c_2$가 된다.

이 때, $\Theta(g(n))$의 $n_0$값은 $n_1, n_2$에서 더 큰 값이 된다.

 

o-notation (small o)

$o(g(n))$ = {f(n): 모든 $n \geq n_0$에 대해서 $0 \leq f(n) \leq cg(n)$를 성립하는 양의 상수 $n_0$값이 있고, 이 때의 c값은 모든 양의 상수 값이 성립된다.}

g(n)은 f(n)의 asymptotic strict upper boud(엄격한 점근적 상계)이다.

 

빅오 표기법에서의 c는 그저 존재하는 값이였지만, 리틀오 표기법에서는 반드시 c값에 모든 양의 상수가 들어갈 수 있어야한다.

o(f(n))이면 O(f(n))이라고 말할 수 있다.

x값이 극한으로 향하면, g(x)가 f(x)보다 훨씬 커지기 때문에 $\lim_{n \rightarrow \infty}\frac{f(x)}{g(x)}= 0$ 라고도 한다.

 

예시를 들면,

$n^{1.9999} = o(n^2)$ 이라고 볼 수 있는데,

$\lim_{n \rightarrow \infty}\frac{n^{1999}}{n^2} = \lim_{n \rightarrow \infty} n^{-0.001} = 0$이기 때문이다.

 

$n^2 \neq o(n^2)$인데, c의 값이 1/2가 되면 f(n)의 값이 더 크기 때문에 안된다.

$\lim_{n \rightarrow \infty}\frac{n^{2}}{n^2} =1$, 리미트로 계산해도 0이 나오지 않기 때문에 성립하지 않는다.

 

$\omega$-notation (small omega)

$\omega(g(n))$ = {f(n): 모든 $n \geq n_0$에 대해서 $0 \leq cg(n) \leq f(n)$를 성립하는 양의 상수 $n_0$값이 있고, 이 때의 c값은 모든 양의 상수 값이 성립된다.}

g(n)은 f(n)의 asymptotic strict lower bound(엄격한 점근적 하계)이다.

 

x값이 극한으로 향하면, f(x)의 값이 g(x)보다 훨씬 커지기 때문에 $\lim_{n \rightarrow \infty}\frac{f(x)}{g(x)}=\infty$ 라고도 한다.

 

예시를 들면,

$n^{2.0001} = \omega(n^2)$ 이다.

---

Comparisons of Functions: 함수의 비교

관련 속성

• Transitivity(추이성): 삼단논법이라고 할 수 있다. $f(n) = \Theta(g(n))$이고, $g(n) = \Theta(h(n))$ 이면, $f(n) = \Theta(h(n))$이다. $O, \Omega, o, \omega$에도 동일하게 적용된다.
• Reflexivity(반사성): 자기 반영이라고 생각하면 될 것 같다. $f(n) = \Theta(f(n))$이다. $O, \Omega$에도 동일하게 적용된다.
• Symmetry(대칭성): $f(n) = \Theta(g(n))$ iff $g(n) = \Theta(f(n))$이다.
• Transpose symmetry: $f(n) = O(g(n)) iff g(n) = \Omega(f(n))$ 이고, $f(n) = \omega(g(n)) iff g(n) = o(f(n))$이다.

비교

• 만약 $f(n) = o(g(n))$이면, f(n)은 g(n)보다 점근적으로 작다.
• 만약 $f(n) = \omega(g(n))$이면, f(n)은 g(n)보다 점근적으로 크다.

+ 실행시간을 함수로 나타내면 계속 증가하는 함수로 나타난다.

---

함수의 그래프를 그려야하는데, 만약 어렵다면 아이패드 수학 메모 기능을 활용하도록 하자.

식을 적으면 그래프를 자동으로 생성해준다. 개꿀 !

 

+ 어디에서는 log라고 표기하고, 어디서는 lg라고 표기하는데 밑은 전부 표기를 안하길래 잠깐 찾아봤다. 정해진 표기법이랑은 다르게 사용하는데, 알고리즘에서는 밑이 표기가 안되어있으면 2라고 생각하면 될 것 같다. (한국이 좀 멋대로 사용하는 것 같기도,,)

 

** 대학교 수업을 듣고 이해한 부분을 최대한 풀어서 작성한 글입니다.

틀린 정보가 존재할 수 있으며, 언제나 피드백은 환영입니다. **