점화식

점화식

• 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현

1. 반복 대치

• 더 작은 문제에 대한 함수로 반복해서 대치해가는 방법

점근적 복잡도 계산 용의

$$ n = c^k $$

• $$
  n , \le , c^k , < , cn , 인, c^k이 , 하나 존재한다.
  $$

• $$
  만약,임의의,상수,r에,대해,T(n),=,O(n^r)이라면,
  $$

  $$
  T(cn) ,=,O((cn)^r),=,O(c^rn^r),=,O(n^r)이므로,T(cn),=,T(n)이,된다.
  $$

• 입력의 크기가 두배가 되어도 다항식 범위 내에 있는 점근적 복잡도는 변하지 않는다.
  $$
  T(n), \le , T(2^k), \le , T(2n)
  $$

2. 추정 후 증명

• 결론을 추정하고 수학적 귀납법으로 이용하여 증명하는 방법

수학적 귀납법의 다양한 가정 및 전개

• $$
  n , =, k일,때 , 성립하면 , n , = , k , + , 1 , 일 , 때도 성립
  $$

• $$
  n_0 , \le , k , < , n ,인 , 모든 , k에 ,대해 ,성립하면 ,n일 ,때도 , 성립
  $$

• $$
  n , = , k일, 때 , 성립하면 , n , = , 2k일 , 때도 , 성립
  $$

3. 마스터 정리

• 형식에 맞는 점화식의 복잡도를 바로 알 수 있다.

형태

• 입력 크기가 n인 문제를 풀기 위해

  입력의 크기가 n/b인 문제를 a개 풀고, 나머지 f(n)의 오버헤드가 필요한 알고리즘

$$ T(n)\, = \, aT(\frac{n}{b}) \, + \, f(n) $$

마스터 정리

중요 부분

$$ a \, \ge \, 1, \, b \, > \, 1에 \, 대해 \, $$

$$
T(n) , = , aT(\frac{n}{b}) , + , f(n)인, 점화식에서
$$

$$
n^{log_ba} , = , h(n)이라 , 할 , 때
$$

$$
T(n)의 , 점근적 복잡도는 다음과 같다.
$$

$$ 1. \, 어떤 \, 양의 \, 상수 \, \epsilon에 \, 대하여 \, \frac{f(n)}{h(n)} \, = \, O(\frac{1}{n^\epsilon}) 이면,\, T(n) \, = \Theta(h(n))\,이다. $$

$$
2. , 어떤, 양의 , 상수 , \epsilon에 , 대하여 , \frac{f(n)}{h(n)} , = , \Omega(n^\epsilon)이고,
$$

$$
어떤 , 상수 , c(<1)와 , 충분히 , 큰 , 모든 , n에 ,대해 , af(\frac{n}{b}) , \le , cf(n)이면 , T(n) , = , \Theta(f(n))이다
$$

$$
3. , \frac{f(n)}{h(n)} , = , \Theta(1)이면 , T(n) , = , \Theta(h(n)logn)이다.
$$

*단순화 버전

1. h(n)이 더 무거우면 h(n)이 수행 시간을 결정한다.

$$

1. , \lim_{n \to \infty}{\frac{f(n)}{h(n)}} , = , 0이면 , T(n) , = , \Theta(h(n))이다.
   $$

2. f(n)이 더 무거우면 f(n)이 수행 시간을 결정한다.

$$
2., \lim_{n \to \infty}{\frac{f(n)}{h(n)}} , = , \infty이고,
$$

$$
충분히,큰,모든,n에,대해,af(\frac{n}{b}),<,f(n)이면,T(n),=,\Theta(f(n))이다.
$$

3. h(n)과 f(n)이 같은 무게이면 h(n)에 logn을 곱한 것이 수행 시간이 된다.

$$
3. , \frac{f(n)}{h(n)} , = , \Theta(1)이면 , T(n) , = , \Theta(h(n)logn)이다.
$$