3. Growth of Functions

알고리즘의 시간 복잡도는 큰 크기의 입력에 대해서만 분석해도 충분하기 때문에, 점근적 시간 복잡도를 주로 고려한다.

3.1. Asymptotic notation

Asymptotic notation, functions, and running times

보통 알고리즘의 점근적 분석은 시간 복잡도에 대해 주로 이루어지지만 메모리에 대해서도 분석하기도 한다.

Θ-notation

함수 g(n)에 대해, \Theta(g(n))은 다음과 같은 함수의 집합이다.

\Theta(g(n)) = \{f(n) : \exists c_{1}, c_{2}, n_{0} > 0 s.t. 0 \leq c_{1} g(n) \leq f(n) \leq c_{2}g(n) \forall n \geq n_{0}\}

이 때 g(n)을 f(n)의 점근적 경계라 한다. 정의로부터 f(n)은 점근적으로 음이 아님이 보장된다. (적당히 큰 n에 대해 항상 양수가 되면 점근적으로 양의 함수라고 한다.)

O-notation

점근적 상한만 존재할 때는 O-표현을 쓴다. 정의는 다음과 같다.

O(g(n)) = \{f(n) : \exists c, n_{0} > 0 s.t. 0 \leq f(n) \leq cg(n) \forall n \geq n_{0}\}

\Theta(g(n)) \in O(g(n))이다.

Ω-notation

점근적 하한은 Ω-표현을 쓴다.

\Omega(g(n)) = \{f(n) : \exists c, n_{0} > 0 s.t. 0 \leq cg(n) \leq f(n) \forall n \geq n_{0}\}

다음 정리가 성립한다.

Theorem 3.1. 두 함수 f(n), g(n)에 대해, f(n) = \Theta(g(n))f(n) = O(g(n))f(n) = \Omega(g(n))임과 동치이다.

Asymptotic notation in equations and inequalities

점근적 표현의 등식은, 좌변에서 어떤 함수를 선택하든 우변에서 적당한 함수가 있어 등식을 만족시킬 수 있음을 뜻한다.

o-notation

점근적으로 유연한 상한은 o-표기법을 쓴다.

o(g(n)) = \{f(n) : \forall c > 0, \exists n_{0} > 0 s.t. 0 \leq f(n) \leq cg(n) \forall n \geq n_{0}\}

이 때 \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0이 성립한다.

ω-notation

점근적으로 유연한 하한은 ω-표기법을 쓴다.

\omega(g(n)) = \{f(n) : \forall c > 0, \exists n_{0} > 0 s.t. 0 \leq cg(n) \leq f(n) \forall n \geq n_{0}\}

이 때 \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty이 성립한다.

Comparing functions

Transitivity:

f(n) = \Theta(g(n)), g(n) = \Theta(h(n)) \Rightarrow f(n) = \Theta(h(n)).

f(n) = \Omega(g(n)), g(n) = \Omega(h(n)) \Rightarrow f(n) = \Omega(h(n)).

f(n) = O(g(n)), g(n) = O(h(n)) \Rightarrow f(n) = O(h(n)).

f(n) = o(g(n)), g(n) = o(h(n)) \Rightarrow f(n) = o(h(n)).

f(n) = \omega(g(n)), g(n) = \omega(h(n)) \Rightarrow f(n) = \omega(h(n)).

Reflexivity:

f(n) = \Theta(f(n)), f(n) = O(f(n)), f(n) = \Omega(f(n))

Symmetry:

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

Transpose symmetry:

f(n) = O(g(n)) \Leftrightarrow g(n)=\Omega(f(n))

f(n) = o(g(n)) \Leftrightarrow g(n)=\omega(f(n))

f(n) = o(g(n))일 때 f(n)을 g(n)보다 점근적으로 작다고 하며, f(n) = \omega(g(n))일 때 f(n)을 g(n)보다 점근적으로 크다고 한다.

두 함수에 대해서 반드시 점근적인 관계가 성립하지는 않는다. nn^{1 + \sin n} 사이에서는 점근적 비교가 가능하지 않다.

3.2. Standard notations and common functions

Monotonicity

m \leq n \Rightarrow f(m) \leq f(n)이면 f(n)을 단조증가라고 한다.

m \leq n \Rightarrow f(m) \geq f(n)이면 f(n)을 단조감소라고 한다.

m < n \Rightarrow f(m) < f(n)이면 f(n)을 강증가라고 한다.

m < n \Rightarrow f(m) > f(n)이면 f(n)을 강감소라고 한다.

Floors and ceilings

실수 x에 대해 x 이하의 정수 중 최대값을 \lfloor x \rfloor, x의 플로어라고 한다.

실수 x에 대해 x 이상의 정수 중 최소값을 \lceil x \rceil, x의 실링이라고 한다.

이 함수들은 둘 다 단조증가이다.

Modular arithmetic

정수 a와 자연수 n에 대해, a \mathrm{mod} n은 a를 n으로 나눈 나머지a - n \lfloor a / n \rfloor이 된다.

(a \mathrm{mod} n) = (b \mathrm{mod} n)일 때 a \equiv b (\mathrm{mod} n)이라 쓰며 a는 법 n에 대해 b와 동치라 한다.

Polynomials

음이 아닌 정수 d에 대해, n에 대한 d차 다항식p(n) = \sum_{i = 0}^{d} a_{i}n^{i} 이다. 이 때 a_{0}, \cdots, a_{d}는 다항식의 계수이며 a_{d} \neq 0이다. 어떤 k에 대해 f(n) = O(n^{k})이면 f(n)이 다항식적으로 유계라고 한다.

Exponentials

n^{b} = o(a^{n})이다.

Logarithms

(\log n)^{b} = o(n^{a})이다. 어떤 k에 대해 f(n) = O((\log n)^{k}) 이라면 f(n)이 다항로그적으로 유계라고 한다.

Factorials

n! \leq n^{n}이다.

n! = \sqrt{2 \pi n} (\frac{n}{e})^{n} (1 + \Theta(\frac{1}{n})) 이 성립한다. (스털링 근사)

Functional iteration

f를 i번 합성한 함수를 f^{(i)}(n)로 표현한다.

The iterated logarithm funtion

순차 로그는 \log^{\ast}(n) = \mathrm{min}\{i \geq 0 : \log^{(i)} n \leq 1\} 로 정의한다. 이는 굉장히 느리게 증가하는 함수이다.

Fibonacci numbers

피보나치 수는 다음의 점화식을 만족하는 수이다.

F_{0} = 0, F_{1} = 1, F_{i} = F_{i-1} + F_{i -2} for i \geq 2.

이는 황금비 \phi 및 그 켤레수 \hat{\phi}와 관계가 있다. F_{i} = \frac{\phi^{i} - \hat{\phi}^{i}}{\sqrt{5}} 가 성립한다.

피보나치 수는 지수적으로 증가한다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중