점화식 이란?

알고리즘을 공부하다가 점화식이라는 키워드가 나와서 알아본 정보입니다.

 

점화식이란 ?

수열의 각 항 간에 관계를 (단순 나열이 아닌 규칙으로) 표현한 관계식을 의미합니다.

좀 더 쉽게 이야기하면? - 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것입니다.

다시 말해 재귀함수의 구조를 갖는 알고리즘만 점화식으로 표현할 수 있습니다.

- 수열의 N 번째 항(일반항) 을, 

- 그 앞의 항들에 의해 규칙적(종속적)으로 표현한 관계식을 말합니다.

 

어떤 점화식 표현이있을까 ?

http://www.ktword.co.kr/test/view/view.php?m_temp1=6008

 

점화식 특징은 ?

등식 또는 관계식 형태를 갖고있습니다. (단, 문제 제시 때는 초기값 또는 경계값이 반드시 필요합니다)

점화식 자체는, 간접적이고 부분적인 정보만 주어, 따라서 일반항을 구할 필요 있습니다.

 

점화식의 점근적 분석방법의 종류는?

1. 반복대치 : 더 작은 문제에 대한 함수로 반복해서 대치함.

2. 추정 후 증명 : 식의 모양을 보고 점근적 복잡도를 추정한 다음, 그것이 옮다는 걸 수학적 귀납법으로 증명

3. 마스터 정리 : 특정 형식에 맞는 점화식의 복잡도를 계산이나 증명없이 알수있는 정리