рекурсии дерева, решения рекуррентных уравнений

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

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

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

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