Рекурсивное дерево, Решающее Рекуррентные уравнения

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

В Интернете есть отличный ресурс, где можно узнать о here. http://www.math.upenn.edu /~wilf/DownldGF.html

Если вы пройдетесь по первой паре примеров, вы должны освоиться с этим в кратчайшие сроки.

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

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