지금까지 내가 재발 방정식을 해결하는 4 가지 방법이 있습니다 알고 : 1 재귀 나무 2 대체 3 - 반복 4 - 파생 우리가 사용하도록 요청재귀 트리,
을 대체하는 경우, , 우리는 산출 공식을 추측해야 할 것입니다. 나는 이것을하기위한 마법이 없다는 것을 CLRS 서적에서 읽었으며, 이것을 할 수있는 경험적 방법이 있다면 나는 궁금했다.
출력이 Big-OH 또는 Theta 형식이므로 수식 트리를 그리거나 반복을 사용하여 확실히 아이디어를 얻을 수 있지만 수식은 반드시 일치하지 않습니다.
대체를 사용하여 되풀이 방정식을 푸는 것에 대한 권장 사항이 있습니까?
단순한 경우에는 "합리적인"추측을하십시오.
더 복잡한 경우 반복 트리를 사용합니다. — 추측을 생성하는 가장 쉬운 "알고리즘"이라고 생각합니다. 바운드를 증명하기 위해 반복 트리를 사용하는 것은 어려울 수 있습니다 (세부 사항은 올바르게 진행하기가 어렵습니다). 되풀이 나무는 추측을 형성하는 데 매우 유용하며 추측은 대체에 의해 증명됩니다.
수식이 Big-O 또는 Theta의 출력과 일치하지 않는다고 말하는 이유가 확실하지 않습니다. 일반적으로 정확히 일치하지는 않지만 Big-O의 요점입니다. 대치로 돌아가는 트릭의 일부는 Big-O 솔루션을 연결하여 대체 대수학을 작동시키는 방법을 아는 것입니다. IIRC, CLRS는이 중 하나 또는 두 가지를 해결합니다.
차갑다. 감사. 나는 그것을 시도 할 것이다. – DarthVader
재발 방정식을 해결할 수있는 방법의 목록은 분명히 완전하지 않습니다. 컴퓨터 과학자를 가르치는 도구 집합은 분명히 완전하지 않습니다. 대부분의 문제를 해결할 가능성이 높기 때문입니다.
반복 방정식의 정확한 해법을 위해 수학자는 생성 함수라는 도구를 사용합니다. 함수를 생성하면 정확한 솔루션을 얻을 수 있으며 일반적으로 마스터 정리보다 강력합니다.
온라인 학습 자료는 여기를 참조하십시오. http://www.math.upenn.edu/~wilf/DownldGF.html
첫 번째 몇 가지 예를 살펴보면 즉시 중단해야합니다.
몇 가지 수학적 배경이 필요하며 기초적인 테일러 시리즈를 이해해야합니다. http://en.wikipedia.org/wiki/Taylor_series
생성 함수 또한 확률에 매우 유용합니다.
아, 나는 모든 반복 방정식에 적용 할 수없는 마스터 정리를 잊었다 – DarthVader