Мастер-теорема

Мастер теорема — теорема позволяющая найти асимптотическое решение (с помощью О - большое нотации) рекуррентных соотношений, которые могут возникнуть во многих алгоритмах, например таких как разделяй и властвуй. Однако не все рекуррентные соотношения могут быть решены через мастер теорему, ее обобщения включаются в метод Акра-Бацци.

Формулировка и доказательство мастер-теоремы

Теорема:

Пусть у нас дано соотношение вида: [math] T(n) = \begin{cases} a \; T\!\left(\frac{n}{b}\right) + n^{c} , & n \gt 1\\ d , & n = 1 \end{cases} [/math] , где [math]a[/math] — количество подзадач, на которые мы разбили нашу задачу, [math]n[/math] — размер нашей задачи, [math]n / b[/math] — размер подзадачи, [math] n ^ {c} [/math] — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач, [math]d[/math] — единичная стоимость для данной задачи. Пусть [math]a[/math] — [math]\mathbb N [/math] число большее 1, [math]b[/math] — [math]\mathbb R [/math] число большее 1, пусть также [math]c[/math] — [math]\mathbb R^{+} [/math] число и [math]d[/math] — [math]\mathbb R^{+} [/math] , тогда возможны три случая: 1. Если [math]c \gt \log_b a[/math], то [math]T(n) = \Theta\left( n^{c} \right)[/math] 2. Если [math]c = \log_b a[/math], то [math]T(n) = \Theta\left( n^{c} \log n \right)[/math] 3. Если [math]c \lt \log_b a[/math], то [math]T(n) = \Theta\left( n^{\log_b a} \right)[/math]

Доказательство:

[math]\triangleright[/math]

Для доказательства мы установим [math]d = 1[/math], это требуется для того, чтобы наши вычисления были хорошо определены при рекурсивном спуске. Давайте рассмотрим дерево рекурсии. Всего в нем будет [math]\log_b n[/math] уровней. На каждом таком уровне, количество подзадач будет умножаться на [math]a[/math], так на уровне [math]i[/math] будет [math]a^i[/math] подзадач. Также известно, что каждая подзадача на уровне [math]i[/math] размера [math]n / b^i[/math]. Подзадача размера [math]n / b^i[/math] требует [math](n / b^i) ^ c[/math] дополнительных затрат, поэтому общее количество совершенных операций на уровне [math]i[/math] : [math]a^i(n / b^i)^c = n^c(a^i/b^(ic)) = n^c(a/b^c)^i[/math] Заметим, что количество занятой памяти увеличивается, уменьшается и остается константой, если [math](a/b^c)^i[/math] увеличивается, уменьшается или остается константой соответственно. Поэтому мы должны разобрать три случая, когда [math](a/b^c)^i[/math] больше 1, равен 1 или меньше 1. Рассмотрим [math](a/b^c)^i = 1[/math] [math]\Leftrightarrow[/math] [math]a = b^c[/math] [math]\Leftrightarrow[/math] [math]\log_b a = c \log_b b[/math] [math]\Leftrightarrow[/math] [math]\log_b a = c[/math]. Распишем всю работу в течение рекурсивного спуска: [math] \displaystyle\sum_{i=1}^{log_b n}n^c(\frac{a}{b^c})^i = n^c\displaystyle\sum_{i=1}^{log_b n}(\frac{a}{b^c})^i[/math] Откуда получаем: 1. [math]\log_b a \lt c \log_b b[/math] [math]\Rightarrow[/math] [math]T(n) = \Theta\left( n^{c} \right)[/math] (т.к. [math] (\frac{a}{b^c})^i[/math] убывающая геометрическая прогрессия) 2. [math]\log_b a = c \log_b b[/math] [math]\Rightarrow[/math] [math] T(n) = \displaystyle\sum_{i=1}^{log_b n}n^c(\frac{a}{b^c})^i = n^c\displaystyle\sum_{i=1}^{log_b n}(\frac{a}{b^c})^i = n^c\displaystyle\sum_{i=1}^{log_b n}1^i = n^c + n^c\log_b n\ = \Theta\left( n^{c} \log n \right) [/math] 3. [math]\log_b a \gt c \log_b b[/math] [math]\Rightarrow[/math] [math]T(n) = \displaystyle\sum_{i=1}^{log_b n}n^c(\frac{a}{b^c})^i = n^c\displaystyle\sum_{i=1}^{log_b n}(\frac{a}{b^c})^i = \Theta\left( n^c(\frac{a}{b^c})^{log_b n} \right)[/math], но [math] n^c(\frac{a}{b^c})^{log_b n} [/math] [math] = [/math] [math] n^c(\frac{a^{log_b n} }{(b^c)^{log_b n}}) [/math] [math] = [/math] [math] n^c(\frac{n^{log_b a}}{n^c})[/math] [math] = [/math] [math] \Theta\left( n^{\log_b a} \right) [/math]

[math]\triangleleft[/math]

Примеры

Пусть у нас задана такое рекуррентное соотношение:

[math] t(x) = \begin{cases} 3 \; t\!\left(\frac{x}{2}\right) + x^{2} , & x \gt 2\\ 5x , & 1 \lt x \lt 2 \end{cases} [/math]

Рассчитать для [math]x = 7[/math].

Заметим, чтобы узнать [math]t(7)[/math] , мы должны знать [math]t(7/2)[/math], чтобы узнать [math]t(7/2)[/math], мы должны узнать [math]t(7/4)[/math], [math]1 \lt  7/4 \lt  2[/math], тогда [math]t(7/4) = 35/4[/math] , [math]t(7/2) = 3*35/4 + 49/4[/math], тогда [math]t(7) = 3t(7/2) + 7^2 = 329/2[/math]

Пусть задано такое соотношение:

[math] T(n) = \begin{cases} 2 \; t\!\left(\n\right) + f(n) , & n \gt 1\\ d , & n = 1 \end{cases} [/math]