Дерево рекурсии, решение рекуррентных уравнений

Насколько мне известно, существует 4 способа решения рекуррентных уравнений: 1- деревья рекурсии 2- подстановка 3- итерация 4- производная

Нас просят использовать Подстановку, которая нам понадобится, чтобы угадать формулу для вывода. Я читал в книге CLRS, что для этого нет никакой магии, мне было любопытно, есть ли какие-либо эвристики для этого?

Я, конечно, могу получить представление, нарисовав дерево повторяемости или используя итерацию, но, поскольку вывод будет в формате Big-OH ​​или Theta, формулы не обязательно совпадают.

Есть ли у кого-нибудь рекомендации по решению рекуррентных уравнений с помощью замены?


recursion recurrence algorithm heuristics
person DarthVader    schedule 06.10.2009    source источник
comment
О, я забыл главную теорему, которую нельзя применить ко всем рекуррентным уравнениям.   -  person DarthVader    schedule 06.10.2009

Ответы (2)


arrow_upward
1
arrow_downward

Для простых, просто сделайте «разумное» предположение.

Для более сложных я бы пошел дальше и использовал дерево повторения, которое мне кажется самым простым «алгоритмом» для генерации предположения. Обратите внимание, что может быть сложно использовать рекуррентное дерево для доказательства границы (детали трудно понять правильно). Деревья повторяемости очень полезны для формирования предположений, которые затем подтверждаются подстановкой.

Я не уверен, почему вы говорите, что формулы не будут совпадать с выводом в Big-O или Theta. Обычно они не совпадают точно, но в этом и заключается смысл Big-O. Часть хитрости возвращения к подстановке заключается в том, чтобы знать, как подключить решение Big-O, чтобы заставить работать алгебру подстановки. IIRC, CLRS действительно работает с одним или двумя примерами из этого.

person Michael Ekstrand    schedule 06.10.2009
comment
Прохладный. Спасибо. Я попробую это. - person DarthVader; 06.10.2009

arrow_upward
3
arrow_downward

Обратите внимание, что список возможных способов решения рекуррентных уравнений определенно не полон, это всего лишь набор инструментов, которым обучают компьютерщиков, потому что они, скорее всего, решат большинство ваших проблем.

Для точных решений рекуррентных уравнений математики используют инструмент, называемый производящими функциями. Производящие функции дают вам точные решения и, как правило, более эффективны, чем основная теорема.

Существует отличный ресурс в Интернете, чтобы узнать об этом здесь. http://www.math.upenn.edu/~wilf/DownldGF.html< /а>

Если вы пройдете первые пару примеров, вы быстро освоитесь.

Вам нужны математические знания и понимание простейших серий Тейлора. http://en.wikipedia.org/wiki/Taylor_series

Производящие функции также чрезвычайно полезны в теории вероятностей.

person ldog    schedule 06.10.2009