점화식 Recusion Tree로 풀기

 

[ 점화식 기본 수식 ]

재귀의 기초 지식 내용을 알아보기 전에 아래의 수식이 어떤 시간 복잡도를 가지고 있는지를 눈으로 읽혀둔다. 처음 봤을 때는 이게 무슨 말인지 모를 수도 있지만, 나중에 딱 이 수식만을 알기 위해 찾을 경우가 존재하므로 글의 가장 상단에 위치시켰다.

 

하나의 항목을 제거하기 위해 입력을 반복하는 재귀 알고리즘이다.

$$T(n) = T(n-1) + n => O(n^2)$$

 

입력을 2개로 분할 후, 정렬 작업을 수행하는 재귀 알고리즘이다.(Quick Sort, Merge Sort)

$$T(n) = 2T(n/2) + cn => O(nlogn)$$

 

하나의 단계마다 입력을 절반으로 줄이는 재귀 알고리즘이다.(Binary Search)

$$T(n) = T(n/2) + c => O(logn)$$

 

입력을 반으로 줄이지만, 입력의 모든 항목을 검사해야하는 재귀 알고리즘이다.(Quick Select)

$$T(n) = T(n/2) + n => O(n)$$

 

입력을 2 개로 분할하고 일정한 양의 다른 작업을 수행하는 재귀 알고리즘이다.

$$T(n) = 2T(n/2) + 1 => O(n)$$

 

이건 참고사항으로 알아두자.

$$T(n) = 4T(n/2) + cn => O(n^2)$$

$$T(n) = 3T(n/4) + cn^2 => O(n^2)$$

$$T(n) = 2T(n/2) + n^2 => O(n^2)$$

 

 

[ 점화식이란 ]

점화식은 수학적으로 풀 수 있는 수식이 아니고 관계식이다. 아래 관계식을 풀이하면 이렇다. T(n)이라는 점화식은 한번 트리를 구성할 때 2개의 T(Tree)가 만들어진다. 2개의 T 중 한개는 T(n/3)이고 다른 하나는 T(2n/3)이다. 이 두개 트리의 가지의 동일 선상의 처리량을 cn이라고 한다. 그리고 모든 가지의 처리량을 모으면 $O(nlogn)$이다.

$$T(n) = T(n/3) + T(2n/3) + cn$$

 

 

 

[ 일반항, 레벨K, 그리고 Cost ]

점화식에서 일반항이란 가장 긴 트리의 가지를 말한다. $1 \over 3$ 보다 $2 \over 3$ 가 더 크다. 이말은 $2 \over 3$ 의 가지가 더 길다는 뜻이다. 위에서 가장 긴 가지는 계속 가지가 뻗어나갔을 때 c($2 \over 3$)$^k$n 이고 이걸 일반항 $({2\over3})^kn$ 이라고 한다. 일반항에서 레벨인 k를 구하는 식은 ($2 \over 3$)$^k$n = 1이고 k = $log_{3\over2}$n 가 된다. 반복되는 가장 큰 값인 일반항을 알면 레벨K는 바로 구할 수 있는 것이다.

 

트리는 l(eft)보다 r(ight)이 더 긴게 뻗어나가고 l x n <= t(n) <= r x n 가 된다. 이건 시간 복잡도 $\Omega$() <= t(n) <= $O$() 를 말한다. l의 레벨은 (${1 \over 3}$)$^k$n = 1 이고 $\log_{3}n$ 이다. r은 $\log_{3\over2}n$ 으로 l보다 길다.

 

전체 Cost를 알기위해서는 $T(n) = \sum\limits_{i=0}^{log_{3\over2}n}cn$ 를 계산해야 한다. ${cn}\sum\limits_{i=0}^{log_{3\over2}n}1$ 이 되고 이건 $cn+cn+....+cn$ = $\log_{3\over2}n+1$ 과 같다.  이 말은 $cn(1+1+1+...+1)$ = $cn(\log_{3\over2}n+1)$ 이라는 말과 같다. 마지막으로 cn보다 $cn\log_{3\over2}n$ 이 더 긴 시간을 가지므로 cn은 무시되어 $O(nlogn)$ 이 된다.

$$cn(log_{3\over2}n+1) = cn\log_{3\over2}n+cn$$

$$cn\log_{3\over2}n+cn = cn\log_{3\over2}n$$

$$cn\log_{3\over2}n = O(nlogn)$$