59
правок
Изменения
Нет описания правки
'''Мастер теорема''' (англ. Master theorem) теорема позволяющая позволяет найти асимптотическое решение рекуррентных соотношений, которые могут возникнуть в реализации анализе асимптотики многих алгоритмов. Однако не все рекуррентные соотношения могут быть решены через мастер теорему, ее обобщения включаются в метод [http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method Акра-Бацци].
==Формулировка и доказательство мастер-теоремы==
<tex dpi = "135"> T(n) = \begin{cases}
a \; T\!\left(\fracdfrac{n}{b}\right) + n^{c} , & n > 1\\
d , & n = 1
\end{cases}
</tex>
где <math>a</math> — количество подзадач, на которые мы разбиваем нашу задачу, <math>n</math> — размер нашей задачи, <tex dpi = "145">\fracdfrac{n}{b}</tex> — размер подзадачи, <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> , тогда решение данного рекуррентного соотношения разбивается на три возможных случая:
|proof= Для доказательства мы установим <math>d = 1</math>, это требуется для того, чтобы при рекурсивном спуске не возникало огромных вычислений.
Давайте рассмотрим дерево рекурсии. Всего в нем будет <math>\log_b n</math> уровней. На каждом таком уровне, количество подзадач будет умножаться на <math>a</math>, так на уровне <math>i</math> будет <math>a^i</math> подзадач. Также известно, что каждая подзадача на уровне <math>i</math> размера <mathtex dpi = "140">\dfrac{n / }{b^i}</mathtex>. Подзадача размера <mathtex dpi = "140">\dfrac{n / }{b^i}</mathtex> требует <mathtex dpi = "140">(\dfrac{n / }{b^i}) ^ c</mathtex> дополнительных затрат, поэтому общее количество совершенных операций на уровне <math>i</math> : <mathtex dpi = "140">a^i(\dfrac{n / }{b^i})^c = n^c(\dfrac{a^i/}{b^{ic}}) = n^c(\dfrac{a/}{b^c})^i</mathtex>Заметим, что количество операций увеличивается, уменьшается и остается константой, если <mathtex dpi = "140">(\dfrac{a/}{b^c})^i</mathtex> увеличивается, уменьшается или остается константой соответственно.Поэтому мы должны разобрать три случая, когда <mathtex dpi = "132">(\dfrac{a/}{b^c})^i</mathtex> больше <math>1</math>, равен <math>1</math> или меньше <math>1</math>.Рассмотрим <mathtex dpi = "140">(\dfrac{a/}{b^c})^i = 1</mathtex> <mathtex dpi = "140">\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</mathtex>.
Распишем всю работу в течение рекурсивного спуска:
<tex dpi = "130"> \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</tex>
=== Примеры задач ===
==== Пример 1 ====1.Пусть задано такое рекуррентное соотношение:
Рассчитать для <math>x = 7</math>.
</math>
Заметим, чтобы узнать <math>t(7)</math> , мы должны знать <math>t(7/2)</math>, чтобы узнать <math>t(7/2)</math>, мы должны узнать <math>t(7/4)</math>, <math>1 < 7/4 < 2</math>, тогда <math>t(7/4) = 35/4</math> , <math>t(7/2) = 3*35\cdot35/4 + 49/4</math>, тогда <math>t(7) = 3t(7/2) + 7^2 = 329/2</math>
==== Пример 2 ====2. Задано такое соотношение:
<math>f(n) =</math> <math>n\sqrt{n + 1}</math>
</math>
<mathtex>f(n) = n\sqrt {n + 1} > \ge n\sqrt n = n^{3/2} = O(n^{3/2}) </mathtex>, а также
<math>f(n) = n\sqrt {n + 1} < n\sqrt{n + n} < n\sqrt{2n} = O(n^{3/2}) </math>
Данное соотношение подходит под первый случай (<math>a = 2, b = 3, c = \dfrac{3}{2}</math>), поэтому его асимптотика совпадает с асимптотикой <math>f(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>, т.к. <tex dpi = "145"> \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} < n^r \epsilon</tex>, для любого r <tex dpi = "145">\epsilon > 0</tex>
*<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> не положительна
{| class="wikitable"
|-
| По мастер-теореме <math>c = \log_b a</math>, где <math>a = 1, b = 2, c = 0</math>
|-
| Обход [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0,_%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F [двоичного дерева]]
| <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(1)</math>
| <math>O(n)</math>
* [https://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Dartmouth university — the master theorem]
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4
== Примечание ==
[http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method Метод Акра-Бацци.]
== См.также ==
