[CLRS] [4-3] The substitution method

1. Introduction

- 분할 정복(DIvide & conquer)알고리즘의 시간복잡도를 구할 수 있는 네가지 방법중
가장 일반적인 "substitution method"에 대해 알아보자.

- "substitution method"은 두가지 단계로 구성되어 있다.

1)  해당 알고리즘의 시간복잡도를 n에 대한 함수로 가정

2)  수학적 귀납법을 사용하여 그 해가 성립하는지 증명하고, 해당 상수를 찾아낸다.

 

2. Substitution Method

- Substitution Method을 사용하면 재귀 알고리즘에서 상한 또는 하한을 설정가능하다(Big-O , Big-Omega)

- 해당 방법을 이용하기 위해선 Big-Theta를 증명하려고 하기보단, 

- Big-O를 먼저 증명하고 그 다음에 Big-Omega를 증명한후 그 두개를 합쳐서 Big-Theta를 유도하는게 좋다.

- 다음 예시를 통해서, 해당 재귀 알고리즘의 Big-O를 구해보자.

ex)

- 우선 T(n)이 O(nlog2(n) + n)라고 가정하는 것이다. (이때의 가정은 정말 직관으로 예측해야한다.)

- 그 후 귀납에 의한 증명을 다음과 같이 하면 된다.

 

i) n = 1, 성립함을 보이자.

1 * log2(1) + 1 = 0 + 1 = O(1)

 

ii) n보다 작은 임의의 k에 대해 성립한다고 가정해보자.

k * log2(k) + k = O(K) 라고 할때,

 

iii) k/2 일때도 성립함을 보이자.

- T(n) = nlog2(n) + n = O(nlogn) 임을 알 수 있다.

- 즉 Substitution method는 가정을 제대로 설계하지 않으면 증명이 불가능하다는 단점이 존재한다.

 

3. reference

https://velog.io/@dandyoung/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EC%9D%98-%EA%B3%84%EC%82%B0%EB%B3%B5%EC%9E%A1%EB%8F%84