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

2019-09-16T09:06:03Z

213.87.133.9: /* Пример 1 */

'''Мастер теорема''' (англ. ''Master theorem'') позволяет найти асимптотическое решение рекуррентных соотношений, которые могут возникнуть в анализе асимптотики многих алгоритмов. Однако не все рекуррентные соотношения могут быть решены через мастер теорему, ее обобщения включаются в метод Акра-Бацци<ref>[http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method Википедия {{---}} Метод Акра-Бацци]</ref>.

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

Теорема
|about =
мастер-теорема
|statement=
Пусть имеется рекуррентное соотношения:

<tex dpi = "135"> T(n) = \begin{cases}
a \; T\!\left(\dfrac{n}{b}\right) + O(n^{c}) , & n > 1\\
O(1) , & n = 1
\end{cases}
, </tex>

где <tex>a</tex> <tex>\in \mathbb N </tex>, <tex>b</tex> <tex> \in \mathbb R </tex>, <tex> b > 1</tex>, <tex>c</tex> <tex>\mathbb \in R^{+} </tex>.

Тогда асимптотическое решение имеет вид:

# Если <tex>c > \log_b a</tex>, то <tex>T(n) = O\left( n^{c} \right)</tex>
# Если <tex>c = \log_b a</tex>, то <tex>T(n) = O\left( n^{c} \log n \right)</tex>
# Если <tex>c < \log_b a</tex>, то <tex>T(n) = O\left( n^{\log_b a} \right)</tex>

|proof= Рассмотрим дерево рекурсии данного соотношения. Всего в нем будет <tex>\log_b n</tex> уровней. На каждом таком уровне, количество детей в дереве будет умножаться на <tex>a</tex>, так на уровне <tex>i</tex> будет <tex>a^i</tex> детей. Также известно, что каждый ребенок на уровне <tex>i</tex> размера <tex>\dfrac{n}{b^i}</tex>. Ребенок размера <tex>\left(\dfrac{n}{b^i}\right)</tex> требует <tex>O\left(\left(\dfrac{n}{b^i}\right) ^ c\right)</tex> дополнительных затрат, поэтому общее количество совершенных действий на уровне <tex>i</tex> :
<tex> 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)</tex>
Заметим, что количество операций увеличивается, уменьшается и остается константой, если <tex>\left(\dfrac{a}{b^c}\right)^i</tex> увеличивается, уменьшается или остается константой соответственно.

Поэтому решение разбивается на три случая, когда <tex>\dfrac{a}{b^c}</tex> больше <tex>1</tex>, равна <math>1</math> или меньше <math>1</math>. Рассмотрим <tex dpi = "130">\dfrac{a}{b^c}\ = 1\Leftrightarrow a = b^c \Leftrightarrow\ \log_b a = c \log_b b \Leftrightarrow\ \log_b a = c</tex>.

Распишем всю работу в течение рекурсивного спуска:
<tex dpi = "130">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)</tex>

Откуда получаем:

#<tex>c > \log_b a </tex> <tex>\Rightarrow</tex> <tex>T(n) = O\left( n^{c} \right)</tex> (так как <tex dpi = "130"> \left(\dfrac{a}{b^c}\right)^i</tex> убывающая геометрическая прогрессия)
#<tex>c = \log_b a </tex> <tex>\Rightarrow</tex> <tex dpi = "130"> T(n) = \displaystyle\sum_{i=0}^{\log_b n}n^c\cdot\left(\frac{a}{b^c}\right)^i = </tex> <tex dpi = "130> 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) </tex>
#<tex>c < \log_b a </tex> <tex>\Rightarrow</tex> <tex dpi = "125"> 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)</tex>, но <tex dpi = "130"> n^c\cdot\left(\dfrac{a}{b^c}\right)^{\log_b n} </tex> <tex dpi = "130"> = </tex> <tex dpi = "130"> n^c\cdot\left(\dfrac{a^{\log_b n} }{(b^c)^{\log_b n}}\right) </tex> <tex dpi = "130"> = </tex> <tex dpi = "130"> n^c\cdot\left(\dfrac{n^{\log_b a}}{n^c}\right)</tex> <tex dpi = "130"> = </tex> <tex dpi = "130"> n^{\log_b a} \Rightarrow T(n) = O\left(n^{\log_b a}\right)</tex>

}}
Мастер-теорема имеет прямое отношение к анализу алгоритмов, так как рекуррентное соотношение можно воспринимать следующим образом: имеется задача размера <tex> n </tex>, алгоритм разбивает её на <tex> a </tex> подзадач размера <tex> \dfrac{n}{b} </tex> , тратит дополнительно <tex> O(n^c) </tex> действий, а если размер подзадачи становится равен единице, то алгоритму требуется <tex>O(1)</tex> действий на её решение.

Из доказательства теоремы видно, что если в рекурретном соотношении заменить <tex> O </tex> на <tex> \Theta </tex> и <tex> \Omega </tex>, то и асимптотика решения изменится соответствующим образом на <tex> \Theta </tex> или <tex> \Omega </tex>.

==Примеры==

=== Примеры задач ===
==== Пример 1 ====
Пусть задано такое рекуррентное соотношение:

<tex> t(n) = \begin{cases}
2 \; t\!\left(\dfrac{n}{2}\right) + O(n\log n) , & n > 1\\
1 , & n = 1
\end{cases}
</tex>

Заметим, что <tex> n\log n = O(n^c) </tex>, для любого <tex> c > 1 </tex>, что удовлетворяет 1 условию. Тогда <tex> T(n) = O(n^c) </tex>, где <tex> c > 1 </tex>, при <tex> a = 2, b = 2, \log_b a = 1</tex>

==== Пример 2 ====
Задано такое соотношение:

<tex>f(n) =</tex> <tex>n\sqrt{n + 1}</tex>

<tex> T(n) = \begin{cases}
2 \; T\!\left(\dfrac{n}{3}\right) + O(f(n)) , & n > 1\\
d , & n = 1
\end{cases}
</tex>

<tex>f(n) = n\sqrt {n + 1} < n\sqrt{n + n} < n\sqrt{2n} = O(n^{3/2}) </tex>

Данное соотношение подходит под первый случай <tex>\left(a = 2, b = 3, c = \dfrac{3}{2}\right)</tex>, поэтому его асимптотика совпадает с асимптотикой <tex>O(f(n))</tex>.

=== Недопустимые соотношения ===
Рассмотрим пару соотношений, которые нельзя решить мастер-теоремой:
*<tex dpi = "130">T(n) = 2^nT\left (\dfrac{n}{2}\right )+O(n^n)</tex>
*:<tex>a</tex> не является константой; количество подзадач может меняться,
*<tex dpi = "130">T(n) = 2T\left (\dfrac{n}{2}\right )+O\left(\dfrac{n}{\log n}\right)</tex>
*:рассмотрим <tex> f(n) = \dfrac{n}{\log n} </tex> , тогда не существует такого <tex> O(n^c) </tex>, что <tex> f(n) \in O(n^c) </tex>, так как при <tex> n = 1 , f(n) \rightarrow \!\, \infty </tex>, а <tex> O(n^c) </tex> ограничено,
*<tex dpi = "130">T(n) = 0.5T\left (\dfrac{n}{2}\right )+O(n)</tex>
*:<tex>|a| < 1</tex>, однако пример можно решить следующим образом: заметим, что на <tex> i </tex> шаге, размер <tex> T(i) \leqslant \dfrac{c \cdot n}{4^i} </tex> , тогда, оценивая сумму, получаем, что <tex> T(n) = O(n) </tex>,
*<tex dpi = "130">T(n) = -2T\left (\dfrac{n}{3}\right )+O(n^2)</tex>
*:<tex> a < 0 </tex>, при составлении асимптотического решения перед <tex> O </tex> каждый раз будет новый знак, что противоречит мастер-теореме.

=== Приложение к известным алгоритмам ===
{| class="wikitable"
|-
! Алгоритм
! Рекуррентное соотношение
! Время работы
! Комментарий
|-
| [[Целочисленный двоичный поиск]]
| <tex>T(n) = T\left(\dfrac{n}{2}\right) + O(1)</tex>
| <tex>O(\log n)</tex>
| По мастер-теореме <tex>c = \log_b a</tex>, где <tex>a = 1, b = 2, c = 0</tex>
|-
| [[Дерево поиска, наивная реализация | Обход бинарного дерева]]
| <tex>T(n) = 2 T\left(\dfrac{n}{2}\right) + O(1)</tex>
| <tex>O(n)</tex>
| По мастер-теореме <tex>c < \log_b a</tex>, где <tex>a = 2, b = 2, c = 0</tex>
|-
| [[Сортировка слиянием]]
| <tex>T(n) = 2 T\left(\dfrac{n}{2}\right) + O(n)</tex>
| <tex>O(n \log n)</tex>
| По мастер-теореме <tex>c = \log_b a</tex>, где <tex>a = 2, b = 2, c = 1</tex>
|}

== См.также ==
* [[Амортизационный анализ]]

== Примечания ==
<references />

== Источники информации ==
* [http://en.wikipedia.org/wiki/Master_theorem Википедия — Мастер-теорема]
* [https://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Dartmouth university — The master theorem]
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание.стр. 110 М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Амортизационный анализ]]

Викиконспекты - Вклад участника [ru]

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