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

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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