[알고리즘 기초] 04 치환법(Substitution Method)

※ 치환법 2단계

 ① 해의 모양을 추측한다.

 ② 상수들의 값을 찾아내기 위해 수학적 귀납법을 사용하고 그 해가 제대로 동작함을 보인다.

---

Example)

■ Recurrence : $T(n) = 2T(\left\lfloor n/2 \right \rfloor) + n$

 

▶ Guess : $T(n) = O(n \lg n)$ 

▶ Prove by induction : $T(n) \le c \cdot n \lg n$, 어떤 상수 $c>0$에 대해 만족해야 함

                               $O(g(n)) =$ {$f(n): n_{0} \le n, 0 \le f(n) \le c \cdot g(n)$}

▶ Inductive assumption :

$n < k$가 참이면, (즉, $T(n) \le c\cdot n\lg n $)

$n=k$ 또한 참임을 만족시켜야 한다.

특히, $n=\left\lfloor k/2 \right\rfloor$에 대해 만족해야 한다. (즉, $T(\left\lfloor k/2 \right\rfloor) \le c \cdot \left\lfloor k/2 \right\rfloor$ $\cdot $ $\lg \left\lfloor k/2 \right\rfloor$)

 

$T(k)=2T(\left\lfloor k/2 \right\rfloor)+k$

 

위의 식에 부등식을 대체(치환)하면,

$T(k) \le 2(c \cdot \left\lfloor k/2 \right\rfloor \lg \left\lfloor k/2 \right\rfloor) + k$

            $\le 2 \cdot c \cdot k/2 \cdot \lg k/2 + k$

            $\le c \cdot k \cdot \lg k/2 + k$

            $\le c \cdot k $ ( $\lg k - \lg 2$ ) $+k$

            $\le c \cdot k $ ( $\lg k - 1$ ) $+k$

            $\le c \cdot k \lg k - c \cdot k + k$

            $\le c \cdot k \lg k + (1 - c)k$

 

$\therefore$ $c \ge 1$, $T(k) \le c \cdot k \lg k$