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