[알고리즘] 점화식(Recurrence Relation)

점화식(Recurrence Relation)은 수열의 일반항을 한 개 이상의 앞선 항들을 이용하여 나타낸 식이다. 즉, 어떤 함수를 표현할 때 자신보다 더 작은 변수에 대한 함수와의 관계나 자신과 똑같은 함수를 이용해 나타내는 것으로, 이는 자기 호출을 사용하는 함수(재귀)의 복잡도를 구하는데 유용하게 사용된다.

 

 

점화식은 n마다 단계적으로 답을 구함으로써 문제를 푸는 방법이며, 점화 관계(Recurrence Relation)라고 부르기도 한다. 그리고 등차수열, 등비수열, 피보나치수열 등에서 점화식이 사용되고 있다.

​

병합 정렬을 이용하여 점화식의 수행 시간을 계산할 수 있는데, 먼저 입력의 크기가 n인 배열을 이등분한 다음 두 그룹을 각각 정렬하여 병합한 후 다시 정렬해 준다. 이때 입력의 크기가 n인 병합 정렬 시간은 크기가 n/2인 병합 정렬을 두 번 하는 시간과 나머지 오버헤드를 더한 시간이다.

 

 

알고리즘 분석은 보통 점근적(Asymptotic) 의미로 복잡도를 계산하는데, O, Ω, θ 표기법과 같은 방법으로 알고리즘 효율성을 분석할 수 있다. 점근적 표기법을 사용하는 이유는 같은 알고리즘이라도 입력 자료의 크기에 따라 수행 시간에 차이가 나는 것을 보완하기 위해 사용한다. 수행 시간의 차이는 상수로 나타나는데, 이 상수를 숨은 상수(Hidden Constant)라고 한다. 그리고 점화식의 점근적 분석 방법에는 반복 대치, 추정 후 증명, 마스터 정리가 있다.

​

1. 반복 대치는 점화식을 더 작은 변수에 대한 점화식으로 대치하는 작업을 반복하면서 경계 조건에 이를 때까지 전개하는 방법이다.

​

2. 추정 후 증명은 점근적 복잡도를 추정(가정) 한 다음 수학적 귀납법 원리를 이용해 귀납적으로 증명하는 방법이다.

​

3. 마스터 정리는 점화식의 점근적 복잡도를 복잡한 계산이나 증명 없이 바로 알 수 있는 방법으로, 아주 많은 알고리즘이 이에 해당되어 유용한 방법이다.