FL4G{##st4rbuucks##}

recursion : 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 접근하는 방식

ex) 하노이의 탑

Hanoi(n, from, temp, to) {
	if n = 1 then print("move ring on" from "to" to);
	if n > 1 then {
		Hanoi(n-1, from, to, temp);
		Hanoi(1, from, temp, to);
		Hanoi(n-1, temp, from, to);
	}
}

induction method : 자신보다 작은 문제에 대해 결론이 옳음을 가정하고 자신과 이 작은 문제의 관계를 통해서 자신에게도 결론이 옳음을 보이는 것

ex) 하노이의 탑 원판 이동 횟수

H(n) : 하노이 탑 원판 개수가 n일때 최소 원판 이동 횟수

H(1) = 1

H(n) = H(n-1) + H(n-1) = 2H(N-1) + 1

점근적 분석 (Asymptotic Analysis)

$$O-표기법$$

$$O(g(n)) = \{f(n)~|~ \exists c > 0,~n_0 > 0~s.t.~\forall n\ge n_0 ,~f(n) \le cg(n) \}$$

$$\Omega-표기법$$

$$\Omega(g(n)) = \{f(n)~|~\exists c > 0,~n_0 > 0~s.t.~\forall n\ge n_0 ,~cg(n) \le f(n) \}$$

$$\Theta-표기법$$

$$\Theta(g(n)) = O(g(n)) \cap \Omega(g(n))$$

$$\Theta(g(n)) = \{f(n)~|~\exists c_1 ,~c_2 > 0,~n_0 > 0,~s.t.~\forall n\ge n_0 ,~c_1 g(n) \le f(n) \le c_2 g(n)\}$$

$$o-표기법$$

$$o(g(n)) = \{f(n)~|~\displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} =0\}$$

$$o(g(n)) = \{f(n)~|~\exists n_0 > 0~s.t.~\forall c >0~and~n\ge n_0,~f(n)<cg(n)\}$$

$$\omega-표기법$$

$$\omega(g(n)) = \{f(n)~|~\displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} =\infty\}$$

$$\omega(g(n)) = \{f(n)~|~\exists n_0 > 0~s.t.~\forall c > 0~and~\forall n\ge n_0,~cg(n) < f(n)\}$$