재귀 트리, 재발 방정식 해결

Question

내가 아는 한, 재발 방정식을 해결하는 4 가지 방법이 있습니다 : 1- 재귀 트리 2- 대체 3- 반복 4- 파생물

우리는 대체를 사용하도록 요청받으며, 이는 출력 공식을 추측해야합니다. CLRS 책 에서이 일을 할 마법이 없다는 것을 읽었습니다.이 작업을 수행 할 휴리스틱이 있는지 궁금했습니다.

반복 트리를 그리거나 반복을 사용하여 아이디어를 얻을 수 있지만 출력이 큰 O 또는 Theta 형식이므로 공식이 반드시 일치하지는 않습니다.

치환을 사용하여 재발 방정식을 해결하기위한 권장 사항이 있습니까?

Answer 1

간단한 사람들의 경우 "합리적인"추측을하십시오.

더 복잡한 사람들의 경우, 나는 재발 트리를 사용하여 추측을 생성하기위한 가장 쉬운 "알고리즘"인 것 같습니다. 바운드를 증명하기 위해 재발 나무를 사용하기가 어려울 수 있습니다 (세부 사항은 제대로되기가 어렵습니다). 재발 나무는 대체에 의해 입증 된 추측을 형성하는 데 매우 유용합니다.

왜 당신이 공식이 Big-O 또는 Theta의 출력과 일치하지 않는다고 말하는지 잘 모르겠습니다. 그들은 일반적으로 정확히 일치하지 않지만 Big-O의 요점의 일부입니다. 대체로 돌아가는 속임수 중 하나는 대체 대수를 해결하기 위해 Big-O 솔루션을 연결하는 방법을 아는 것입니다. IIRC, CLRS는이 중 하나 또는 두 가지를 해결합니다.

Answer 2

재발 방정식을 해결하는 가능한 방법의 목록은 확실히 완전하지 않으며, 컴퓨터 과학자들이 가르치는 일련의 도구 일뿐입니다. 왜냐하면 그들은 대부분의 문제를 해결할 가능성이 높기 때문입니다.

재발 방정식의 정확한 솔루션을 위해 수학자들은 생성 기능이라는 도구를 사용합니다. 기능을 생성하면 정확한 솔루션을 제공하며 일반적으로 마스터 정리보다 강력합니다.

여기에 대해 배울 수있는 훌륭한 자료가 있습니다. http://www.math.upenn.edu/~wilf/downldgf.html

첫 커플 예제를 살펴보면 즉시 매달려야합니다.

수학 배경이 필요하고 기초적인 Taylor 시리즈를 이해합니다. http://en.wikipedia.org/wiki/taylor_series

생성 함수는 또한 확률로 매우 유용합니다.