귀납적1 [알고리즘] 점화식의 이해(recurrence relation) 점화식 수열의 귀납적 정의와 유사 차이 : 인접한 항간의 관계만을 다루는 것은 아니다. 어떤 함수를 자신보다 더 작은 변수에 대한 함수 자신과의 관계로 표현한 것. (수열 = 정의역이 정수인 함수) 되부름, 혹은 유사한 방식으로 문제를 풀 때 걸리는 시간을 구하는데에 사용함 ex) T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1) + 1 An = T(n), An = 2A(n-1) + 1 점화식을 푸는 법 1. 반복 대치 : 주어진 조건을 이용하여 점점 작은 함수로 반복해서 대치하는 방법. 침착하게 꼼꼼히! 2. 추정 후 증명 : 점화식의 결론을 추정하고, 귀납법으로 증명함. 반복 대치가 복잡할 때 유용함. but 추정이 쉽지 않을 수 있음 3. 마스터 정리 : 점화식 공식. 여기에서는 다.. 2023. 1. 16. 이전 1 다음 728x90 반응형