Основная теорема о скорости роста рекуррентных уравнений

Рекуррентные соотношения и уравнения

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

Как решать рекуррентные соотношения?

Для решения рекуррентных соотношений применяют один из двух основных способов:

  • Метод производящих функций
  • Метод характеристического уравнения

В следующем разделе мы сравним, как выглядит процесс решения для одной и той же последовательности двумя методами.

Метод производящих функций

  1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен $k$) $$a_ <0>= …, \\ a_ <1>= …, \\ a_ = …, \\ … \\ a_ = …, n\geqslant k$$
  2. Домножить каждую строчку на $z$ в соответствующей степени $z^ \cdot a_$ и сложить все выражения для $n \ge 0$. В левой части получится сумма $\displaystyle\sum_^ <\infty>a_nz^n$ — это производящая функция, назовем ее $G(z)$. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее $G(z)$.
  3. Решить полученное уравнение относительно $G(z)$.
  4. Разложить $G(z)$ в степенной ряд, тогда коэффициент при $z_n$ будет искомым выражением для $a_n$.

Метод характеристических функций

Этот метод практически полностью аналогичен методу решения линейных неоднородных дифференциальных уравнений с постоянными коэффициентами, кратко алгоритм выглядит так:

  1. Записать соответствующее однородное рекуррентное уравнение (РУ): $$ p_ a_ + p_a_ + . + p_n a_n =f \to \\ \to p_ a_ + p_a_ + . + p_n a_n =0. $$
  2. Выписать для него характеристическое уравнение и найти его корни $\lambda_i$ $$ p_ \lambda^ + p_\lambda^ + . + p_\lambda + p_n =0. $$
  3. Выписать согласно полученным корням $\lambda_1, . \lambda_k$ общее решение однородного рекуррентного соотношения (подробнее теорию см. по ссылке [1] ниже). $$ C_1 \lambda_1^n +. +C_k \lambda_k^n \, \mbox < для случая различных простых корней>, $$ $$ C_1 \lambda_1^n + C_2 n\lambda_1^n +. +C_m n^m \lambda_1^n+. +C_k \lambda_k^n \mbox < для случая корня >\, \lambda_1 \, < кратности >\, m. $$
  4. Подобрать частное решение неоднородного рекуррентного соотношения по виду правой части (особенно удобно для правых частей вида $\mu^n*P(n)$, $P(n)$ — многочлен от $n$).
  5. Представить общее решение неоднородного РУ как сумму общего решения соответствующего однородного РУ и частного решения неоднородного РУ.
  6. Подставить начальные условия $a_0, a_1, . a_$ и получить значения констант $C_1, . C_k$.

Решение для последовательности чисел Фибоначчи

Последовательность чисел Фибоначи — это последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:

$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 , . $$

Числа Фибоначчи растут быстро: $f_<10>=55$, $f_<20>=6765$, а $f_<100>=354224848179261915075$.

Общая формула данной рекуррентной последовательности имеет вид6

Способ 1. Производящяя функция

Начинаем с второго шага алгоритма, домножаем на $z^n$:

$$\begin 1\cdot f_0 &= &0\cdot 1,\\ z\cdot f_1 &= &1\cdot z,\\ z\cdot f_n & = &(f_+f_)\cdot z^n, \quad n\geq2.\\ \end $$

Складываем все строчки:

На третьем шаге алгоритма приводим все суммы к замкнутому виду:

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

Теперь разложим ее в степенной ряд. Для этого сначала разложим знаменатель на множители. Найдем корни уравнения:

Чтобы разложить данные дроби в ряды, используем известное разложение для дроби:

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на $z_1$:

Аналогично (но с делением на $z_2$) действуем со второй дробью:

Преобразуем данное выражение, используя то, что

$$1/z_1=-z_2, \quad 1/z_2 = -z_1, \quad z_1-z_2=\sqrt <5>$$ $$f_n=\frac<1><\sqrt<5>>\left( \biggl( \frac<1+\sqrt<5>> <2>\biggr)^n — \biggl( \frac<1-\sqrt<5>> <2>\biggr)^n \right). $$

Способ 2. Характеристическое уравнение

Запишем характеристический многочлен для $f_n=f_+f_$, и найдем его корни:

Тогда общее решение однородного рекуррентного уравнения имеет вид:

Осталось найти значения произвольных постоянных $C_1, C_2$ из начальных условий $f_0=0, f_1=1$.

Решая систему, найдем

Итоговое выражение для последовательности чисел Фибоначчи:

Результаты обоих методов совпали, решение вторым методом оказалось проще и короче.

Примеры решений

Задача 1. Решить рекуррентное соотношение $f(n+2)=-6f(n+1)+7f(n)+n-3$ с начальными условиями $f(0)=2$ и $f(1)=4$, сделать проверку

Задача 2. Решить рекуррентное соотношение $f(n+2)=-2f(n+1)+3f(n)-3^n$ с начальными условиями $f(0)=1$, $f(1)=3$ и сделать проверку

Задача 3. 1. Решить рекуррентное соотношение $f(n+2) =-5f(n+1) -4f(n) + 3n^2$ с начальными условиями $f(0) = 2$, $f(1) = 3$.
2. Проверить, удовлетворяет ли найденное решение начальным условиям и обращает ли оно рекуррентное соотношение в справедливое тождество.

Задача 4. Найти последовательность $$, удовлетворяющую рекуррентному соотношению $a_ + 4 a_ + 3 a_ = 0$ и начальным условиям $a_1=2$, $a_2=4$.

Основная теорема о рекуррентных соотношениях

В этой статье вы познакомитесь с основной теоремой о рекуррентных соотношениях и узнаете, как использовать ее для решения рекуррентных соотношений.

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

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

Здесь a ≥ 1 и b > 1 — константы, а f(n) — асимптотически положительная функция.

Асимптотически положительная функция — функция, где при достаточно больших значениях n f(n)>0 .

Основная теорема о рекуррентных соотношениях — простой и быстрый способ вычисления временной сложности рекуррентных соотношений (например, «Разделяй и влавствуй»).

Формулировка теоремы

Если a ≥ 1 и b > 1 — константы, а f(n) — асимптотически положительная функция, то временная сложность рекуррентного соотношения задается выражением:

T(n) имеет следующие асимптотические оценки:

  1. Если f(n) = O(n logb a-ϵ ), то T(n) = Θ(n logb a ).
  2. Если f(n) = Θ(n logb a ), то T(n) = Θ(n logb a *log n).
  3. Если f(n) = Ω(n logb a+ϵ ), то T(n) = Θ(f(n)).

ϵ > 0 — константа.

Каждое из этих условий можно интерпретировать следующим образом:

  1. Если стоимость решения подзадач на каждом уровне увеличивается на некий коэффициент, то значение f(n) станет полиномиально меньше, чем n logb a . То есть, временная сложность зависит от стоимости последнего уровня — n logb a .
  2. Если стоимость решения подзадач на каждом уровне примерно одинакова, то значение f(n) станет равно n logb a . То есть, временная сложность будет равна f(n) , умноженной на количество уровней — n logb a *log n.
  3. Если стоимость решения подзадач на каждом уровне уменьшается на некий коэффициент, то значение f(n) станет полиномиально больше, чем n logb a . То есть, временная сложность зависит от стоимости f(n) .

Пример использования

Когда не работает

Основную теорему о рекуррентных соотношениях нельзя использовать в следующих случаях:

  • T(n) не монотонна — например, T(n) = sin n .
  • f(n) не полиномиальна — например, f(n) = 2n .
  • a не константа — например, а = 2n .
  • a .

Теория алгоритмов

Рекурсивные алгоритмы и методы их анализа

Логарифмические тождества

При анализе рекурсивных алгоритмов достаточно часто используются логарифмические тождества, далее предполагается, что, a > 0, b > 0, c > 0, основание логарифма не равно единице:


в записи Q(ln(x)) основание логарифма не существенно, если он больше единицы, т.к. константа скрывается обозначением Q.

Можно показать, что для любого

Методы решения рекурсивных соотношений

В математике разработан ряд методов, с помощью которых можно получить явный вид рекурсивно заданной функции – метод индукции, формальные степенные ряды, метод итераций и т.д. Рассмотрим некоторые из них:

а) Метод индукции

Метод состоит в том, что бы сначала угадать решение, а затем доказать его правильность по индукции. Пример:

f(0)=1
f(n+1)=2*f(n)

Предположение: f(n)=

Базис: если f(n)= , то f(0)=1, что выполнено по определению.

Индукция: Пусть f(n)= , тогда для n+1 f(n+1)= 2 * =

Заметим, что базис существенно влияет на решение, так, например:

Если f(0)=0, то f(n)=0;

если f(0)=1/7, то f(n)=(1/7)*; если f(0)=1/64, то f(n)=(2)

б) Метод итерации (подстановки)

Суть метода состоит в последовательной подстановке – итерации рекурсивного определения, с последующим выявлением общих закономерностей:

Пусть f(n)=3*f(n/4)+n, тогда:

и раскрывая скобки, получаем:

f(n)=n+3*n/4+9*n/16+27*n/64+…+*n/

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

, то окончательно:

Рекурсивные алгоритмы.

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

общем виде, если происходит разделение задачи на b подзадач, которое приводит к необходимости решения a подзадач размерностью n/b, то общий вид функции трудоемкости имеет вид:

fA(n )= a * fA( n/b )+d(n)+U(n) (9.1), где:

d(n) – трудоемкость алгоритма деления задачи на подзадачи,
U(n) – трудоемкость алгоритма объединения полученных решений.

Рассмотрим, например, известный алгоритм сортировки слиянием, принадлежащий Дж. Фон Нейману:

На каждом рекурсивном вызове переданный массив делится пополам, что дает оценку для d(n) =Q (1), далее рекурсивно вызываем сортировку полученных массивов половинной длины (до тех пор, пока длина массива не станет равной единице), и сливаем возвращенные отсортированные массивы за Q (n).

Тогда ожидаемая трудоемкость на сортировку составит:
fA(n )= 2 * fA( n/2 )+ Q (1)+ Q (n)

Тем самым возникает задача о получении оценки сложности функции трудоемкости, заданной в виде (9.1), для произвольных значений a и b.

Основная теорема о рекуррентных соотношениях

Следующая теорема принадлежит Дж. Бентли, Д. Хакен и Дж. Саксу (1980 г.).

Теорема.Пусть a >= 1, b > 1 — константы, g(n) — функция, пусть далее:

Если g(n)=O(), >0, то f(n)=Q()
Пример:f(n) = 8f(n/2)+, тогда f(n) = Q()

) Если g(n)=Q(), то f(n)=Q(*log n)
Пример: fA(n)= 2 * fA( n/2 )+ Q (n), тогда f(n) = Q(n*log n)

Если g(n) = (), e > 0, то f(n)=Q(g(n))
Пример: f(n)=2*f(n/2)+, имеем:

= , и следовательно: f(n) = Q()

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


источники:

http://codechick.io/tutorials/dsa/dsa-master-theorem

http://th-algoritmov.narod.ru/9.htm