[Algorithm] 점화식 점근적 접근 방식(반복 대치, 추정 후 증명)

점화식을 푸는 방법 중에서 반복 대치와 추정 후 증명에 대해 공부해보려 한다.

 

1. 반복 대치
2. 추정 후 증명

반복 대치

점화식을 잘게 쪼개어서 푸는 방법이다.

 

(1) T(n) = T(n-1)  + n 이라는 점화식이 있다고 하자. ( T(1) = 1 )

 

n에 n-1을 넣으면 T(n-1) = T(n-2) + n-1이 된다.

 

그럼 1번 점화식의 우변에 존재하는 T(n-1)에 그대로 대입하면 

 

(2) T(n) = T(n-2)+ n + (n-1)이 된다.

 

원래 1번 점화식의 n에 n-2를 넣으면 T(n-2) = T(n-3) + n-2가 된다.

 

이를 2번 점화식의 우변에 존재하는 T(n-2)에 그대로 대입하면 

 

(3) T(n) = T(n-3) + n +(n-1) + (n-2)가 된다.

 

T(1)을 알고 있고 T(1)이 나올때까지 이를 계속 반복하다보면 

 

T(n) = 1 + 2 + ... + n 이라는 식이 나오고 덧셈 공식을 사용하면 

 

T(n) = n(n+1)/2 라는 식이 나온다.

 

이번엔 좀 더 어려운 T(n) = 2T(n/2) + n를 풀어보려 한다. ( T(1) = 1 )

 

이번엔 n에 n/2, n/4를 대입하는 방식으로 풀어보려 한다.

 

위와 같은 방식으로 T(n/2)를 구하고 원래 점화식의 우변에 대입하는 방식을 해보면 

 

원래 점화식 : T(n) = 2T(n/2) + n

첫 번째 대입 : T(n) = 4T(n/4) + 2n

두 번째 대입 : T(n) = 8T(n/8) + 3n

 

T(1)까지 구해야 하는데 T안의 n이 절반씩 감소하고 T에 곱해지는 수는 두 배씩 증가하고 T 밖에 더해지는 수는 n씩 더해지므로 알아내기가 쉽지가 않다.

 

그래서 치환을 이용하면 쉽게 풀 수 있다. n을 다음과 같이 치환한다. $$ n=2^{k} $$

 

이제 T(n/2), T(n/4), T(n/8)의 경우 아래와 같이 바뀌게 된다. $$ T(2^{k-1}),T(2^{k-2}),T(2^{k-3}) $$

 

이제 k번만큼 반복을 한다면 T(1)까지 구할 수 있고 점화식을 풀어낼 수 있다.

 

풀어낸 점화식은 다음과 같다.$$ T(n)=2^{k}*T(\frac{n}{2^{k}})+kn $$

 

이제 $$ n=2^{k} $$ 여기에서 양변에 밑이 2인 로그를 취하면 $$ k=\log_{2}{(n)} $$이 된다.

 

이를 풀어낸 점화식에 대입하면 $$ T(n)=n+n\log_{2}{n} $$이 된다.

 

즉 시간 복잡도는 다음과 같다. $$ T(n)=O(n\log_{}{n}) $$

 

 

추정 후 증명

추정 후 증명은 문자 그대로 먼저 시간 복잡도를 추정한 다음 이것이 맞는지 증명하는 방식이다.

 

위에서 반복 대치로 풀었던 T(n) = 2T(n/2) + n 점화식을 추정 후 증명 방식으로 풀어보겠다.

 

먼저 다음과 같이 시간 복잡도를 추정해보겠다.

$$ T(n)=O(n\log_{}{n}) $$

빅 오 표기법의 정의에 의해서 아래와 같은 식이 나온다. (c는 상수)

$$ T(n)<=cn\log_{}{n} $$

현재 위 식이 성립한다고 가정을 한 상태이다.

 

양 변에 n/2를 대입하면 아래와 같다.

$$ T(\frac{n}{2})<=\frac{cn}{2}\log_{}{\frac{n}{2}} $$

 

그리고 T(n) = 2T(n/2) + n 원래의 점화식에서 T(n/2)를 대입해보면 위 식이 성립한다고 가정했기 때문에 아래 식도 반드시 성립한다.

 

$$ T(n)<=cn\log_{}{\frac{n}{2}}+n $$

이제 위 식을 분리해보자.

$$ T(n)<=cn\log_{}{n}+n-cn\log_{}{2} $$

 

이제 아래 식이 성립하면 증명을 성공한 것이다.$$ cn\log_{}{n}+n-cn\log_{}{2}<=cn\log_{}{n} $$

 

c가 아래를 만족하면 성립한다.

 $$c>=\frac{1}{\log_{}{2}} $$