Мастер теорема (англ. Master theorem) позволяет найти асимптотическое решение рекуррентных соотношений, которые могут возникнуть в анализе асимптотики многих алгоритмов. Однако не все рекуррентные соотношения могут быть решены через мастер теорему, ее обобщения включаются в метод Акра-Бацци.
Формулировка и доказательство мастер-теоремы
| Теорема: |
Пусть, при реализации алгоритма мы получили соотношение такого вида:
[math] T(n) = \begin{cases}
a \; T\!\left(\dfrac{n}{b}\right) + n^{c} , & n \gt 1\\
d , & n = 1
\end{cases}
[/math]
где [math]a[/math] — количество подзадач, на которые мы разбиваем нашу задачу, [math]n[/math] — размер нашей задачи, [math]\dfrac{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]\dfrac{n}{b^i}[/math]. Подзадача размера [math]\dfrac{n}{b^i}[/math] требует [math](\dfrac{n}{b^i}) ^ c[/math] дополнительных затрат, поэтому общее количество совершенных операций на уровне [math]i[/math] :
[math]a^i(\dfrac{n}{b^i})^c = n^c(\dfrac{a^i}{b^{ic}}) = n^c(\dfrac{a}{b^c})^i[/math]
Заметим, что количество операций увеличивается, уменьшается и остается константой, если [math](\dfrac{a}{b^c})^i[/math] увеличивается, уменьшается или остается константой соответственно.
Поэтому мы должны разобрать три случая, когда [math](\dfrac{a}{b^c})^i[/math] больше [math]1[/math], равен [math]1[/math] или меньше [math]1[/math].
Рассмотрим [math](\dfrac{a}{b^c})^i = 1[/math] [math]\Leftrightarrow a = b^c\Leftrightarrow\ log_b a = c \log_b b\Leftrightarrow\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 [/math] [math]\Rightarrow[/math] [math]T(n) = \Theta\left( n^{c} \right)[/math] (т.к. [math] (\dfrac{a}{b^c})^i[/math] убывающая геометрическая прогрессия)
2. [math]\log_b a = c [/math] [math]\Rightarrow[/math] [math] T(n) = \displaystyle\sum_{i=1}^{\log_b n}n^c\cdot(\frac{a}{b^c})^i = [/math] [math] n^c\cdot\displaystyle\sum_{i=1}^{\log_b n}(\frac{a}{b^c})^i = n^c\cdot\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 [/math] [math]\Rightarrow[/math] [math] T(n) = \displaystyle\sum_{i=1}^{\log_b n}n^c\cdot(\frac{a}{b^c})^i = n^c\cdot\displaystyle\sum_{i=1}^{\log_b n}(\frac{a}{b^c})^i = \Theta\left( n^c\cdot(\frac{a}{b^c})^{log_b n} \right)[/math], но [math] n^c\cdot(\frac{a}{b^c})^{log_b n} [/math] [math] = [/math] [math] n^c\cdot(\frac{a^{log_b n} }{(b^c)^{log_b n}}) [/math] [math] = [/math] [math] n^c\cdot(\frac{n^{log_b a}}{n^c})[/math] [math] = [/math] [math] \Theta\left( n^{\log_b a} \right) [/math] |
| [math]\triangleleft[/math] |
Примеры
Примеры задач
Пример 1
Пусть задано такое рекуррентное соотношение:
Рассчитать для [math]x = 7[/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]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\cdot35/4 + 49/4[/math], тогда [math]t(7) = 3t(7/2) + 7^2 = 329/2[/math]
Пример 2
Задано такое соотношение:
[math]f(n) =[/math] [math]n\sqrt{n + 1}[/math]
[math] T(n) = \begin{cases}
2 \; T\!\left(\frac{n}{3}\right) + f(n) , & n \gt 1\\
d , & n = 1
\end{cases}
[/math]
[math]f(n) = n\sqrt {n + 1} \lt n\sqrt{n + n} \lt n\sqrt{2n} = O(n^{3/2}) [/math]
Данное соотношение подходит под первый случай [math](a = 2, b = 3, c = \dfrac{3}{2})[/math], поэтому его асимптотика совпадает с асимптотикой [math]f(n)[/math]
Недопустимые соотношения
Рассмотрим пару ошибочно-составленных соотношений:
- [math]T(n) = 2^nT\left (\frac{n}{2}\right )+n^n[/math]
- [math]a[/math] не является константой; количество подзадач может меняться
- [math]T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}[/math]
- не полиномиальное различие [math]f(n)[/math] и [math]n^{\log_b a}[/math], т.к. [math]\frac{f(n)}{n^{\log_b a}} = \frac{\frac{n}{\log n}}{n^{log_2 2}} = \frac{n}{n \log n} = \frac{1}{\log n} \lt n^\epsilon[/math], для любого [math]\epsilon \gt 0[/math]
- [math]T(n) = 0.5T\left (\frac{n}{2}\right )+n[/math]
- [math]a[/math] < 1 не может быть меньше одной подзадачи
- [math]T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n[/math]
- [math]f(n)[/math] не положительна
Приложение к известным алгоритмам
| Алгоритм
|
Рекуррентное соотношение
|
Время работы
|
Комментарий
|
| Целочисленный двоичный поиск
|
[math]T(n) = T\left(\frac{n}{2}\right) + O(1)[/math]
|
[math]O(\log n)[/math]
|
По мастер-теореме [math]c = \log_b a[/math], где [math]a = 1, b = 2, c = 0[/math]
|
| Обход двоичного дерева
|
[math]T(n) = 2 T\left(\frac{n}{2}\right) + O(1)[/math]
|
[math]O(n)[/math]
|
По мастер-теореме [math]c \lt \log_b a[/math], где [math]a = 2, b = 2, c = 0[/math]
|
| Сортировка слиянием
|
[math]T(n) = 2 T\left(\frac{n}{2}\right) + O(n)[/math]
|
[math]O(n \log n)[/math]
|
По мастер-теореме [math]c = \log_b a[/math], где [math]a = 2, b = 2, c = 1[/math]
|
Источники информации
Примечание
Метод Акра-Бацци.
См.также
