Изменения

'''Мастер теорема''' — теорема позволяющая (англ. ''Master theorem'') позволяет найти асимптотическое решение (с помощью [https://ru.wikipedia.org/wiki/%C2%ABO%C2%BB_%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%BE%D0%B5_%D0%B8_%C2%ABo%C2%BB_%D0%BC%D0%B0%D0%BB%D0%BE%D0%B5 О - большое нотации]) рекуррентных соотношений, которые могут возникнуть во в анализе асимптотики многих алгоритмах, например таких как разделяй и властвуйалгоритмов. Однако не все рекуррентные соотношения могут быть решены через мастер теорему, ее обобщения включаются в метод Акра-Бацци<ref>[http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method Википедия {{---}} Метод Акра-Бацци]</ref>.

Теорема|about = мастер-теорема|statement=Пусть имеется рекуррентное соотношения: <mathtex dpi = "135"> T(n) = \begin{cases} a \; T\!\left(\fracdfrac{n}{b}\right) + O(n^{c} ) , & n > 1\\ d O(1) , & n = 1

</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^{+} </mathtex> число и <math>d</math> — <math>\mathbb R^{+} </math> , тогда возможны три случая:

1. Если где <tex>a</tex> <tex>\in \mathbb N </tex>, <tex>b<math/tex>c <tex> \log_b ain \mathbb R </tex>, <tex> b > 1</mathtex>, то <mathtex>c</tex> <tex>T(n) = \Thetamathbb \left( nin R^{c+} \right)</mathtex>.

3. # Если <mathtex>c > \log_b a</tex>, то <tex>T(n) = O\left( n^{c } \right)</tex># Если < tex>c = \log_b a</mathtex>, то <mathtex>T(n) = O\left( n^{c} \log n \right)</tex># Если <tex>c < \Thetalog_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=10}^{\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=10}^{\log_b n}\left(\frac{a}{b^c}\right)^i\right)</tex> 

1. #<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> <mathtex 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 </mathtex> <mathtex>\Rightarrow</mathtex> <mathtex dpi = "125">T(n) = \Thetadisplaystyle\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)</mathtex>, но <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(\fracdfrac{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^ic}\right)</tex> <tex dpi = "130"> = </tex> убывающая геометрическая прогрессия <tex dpi = "130"> n^{\log_b a} \Rightarrow T(n) = O\left(n^{\log_b a}\right)</tex>

2. }}Мастер-теорема имеет прямое отношение к анализу алгоритмов, так как рекуррентное соотношение можно воспринимать следующим образом: имеется задача размера <mathtex>\log_b a = c \log_b bn </mathtex> , алгоритм разбивает её на <mathtex>\Rightarrowa </mathtex> подзадач размера <tex dpi = "130"> T(n) = \displaystyle\sum_dfrac{i=1}^{log_b n}n^c(\frac{a}{b^c})^i = </tex> , тратит дополнительно <tex> O(n^c\displaystyle\sum_{i=1}^{log_b n}) </tex> действий, а если размер подзадачи становится равен единице, то алгоритму требуется <tex>O(\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) </tex>действий на её решение.

3. <math>\log_b a > c \log_b b</math> <math>\Rightarrow</math> Из доказательства теоремы видно, что если в рекурретном соотношении заменить <tex dpi = "130">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)O </tex>, но на <tex dpi = "150"> n^c(\frac{a}{b^c})^{log_b n} Theta </tex> и <tex dpi = "130"> = </tex> <tex dpi = "150"> n^c(\frac{a^{log_b n} }{(b^c)^{log_b n}}) </tex> <tex dpi = "130"> = Omega </tex> , то и асимптотика решения изменится соответствующим образом на <tex dpi = "150"> n^c(\frac{n^{log_b a}}{n^c})</tex> <tex dpi = "130"> = Theta </tex> или <tex dpi = "130"> \Theta\left( n^{\log_b a} \right) Omega </tex>.

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

<mathtex> t(xn) = \begin{cases} 3 2 \; t\!\left(\fracdfrac{xn}{2}\right) + x^{2} O(n\log n) , & x n > 21\\ 5x 1 , & n = 1 < x < 2

</mathtex>

Рассчитать для <math>x = 7</math>. Заметим, чтобы узнать что <mathtex>tn\log n = O(7n^c)</mathtex> , мы должны знать для любого <mathtex> c >t(7/2)1 </mathtex>, чтобы узнать что удовлетворяет 1 условию. Тогда <mathtex>tT(7/2n)</math>, мы должны узнать <math>t= O(7/4n^c)</mathtex>, где <mathtex> c >1 < 7/4 < 2</mathtex>, тогда при <mathtex>t(7/4) a = 35/4</math> , <math>t(7/2) = 3*35/4 + 49/4</math>, тогда <math>t(7) b = 3t(7/2) + 7^2 , \log_b a = 329/21</mathtex>

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

</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 [[Категория:Дискретная математика и алгоритмы]][[Категория:Амортизационный анализ]]