Изменения

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

 Теорема|about = мастер-теорема|statement=Пусть, при реализации алгоритма мы получили соотношение такого видаимеется рекуррентное соотношения:

a \; T\!\left(\dfrac{n}{b}\right) + O(n^{c} ) , & n > 1\\ d O(1) , & n = 1

, </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>.

где <math>a</math> — количество подзадач, на которые мы разбиваем нашу задачу, <math>n</math> — размер нашей задачи, <tex dpi = "145">\dfrac{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> , тогда Тогда асимптотическое решение данного рекуррентного соотношения разбивается на три возможных случаяимеет вид:

1. # Если <mathtex>c > \log_b a</mathtex>, то <mathtex>T(n) = O\Thetaleft( 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)</mathtex>

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

3. Если Поэтому решение разбивается на три случая, когда <mathtex>\dfrac{a}{b^c }</tex> больше <tex>1</tex>, равна < \log_b amath>1</math>, то или меньше <math>1</math>T(n) . Рассмотрим <tex dpi = "130">\Thetadfrac{a}{b^c}\ = 1\left( nLeftrightarrow a = b^{c \Leftrightarrow\ \log_b a} = c \log_b b \Leftrightarrow\ \right)log_b a = c</mathtex>.

<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. #<mathtex>c >\log_b a < c </mathtex> <mathtex>\Rightarrow</mathtex> <mathtex>T(n) = \ThetaO\left( n^{c} \right)</mathtex> (т.к. так как <tex dpi = "130"> \left(\fracdfrac{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>

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

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

<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>

Заметим, чтобы узнать что <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\cdot35/4 + 49/4</math>, тогда <math>t(7) b = 3t(7/2) + 7^2 , \log_b a = 329/21</mathtex>

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

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

</mathtex>

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

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

| <mathtex>T(n) = T\left(\fracdfrac{n}{2}\right) + O(1)</mathtex>| <mathtex>O(\log n)</mathtex>| По мастер-теореме <mathtex>c = \log_b a</mathtex>, где <mathtex>a = 1, b = 2, c = 0</mathtex>

| Обход [[двоичного Дерево поиска, наивная реализация | Обход бинарного дерева]]| <mathtex>T(n) = 2 T\left(\fracdfrac{n}{2}\right) + O(1)</mathtex>| <mathtex>O(n)</mathtex>| По мастер-теореме <mathtex>c < \log_b a</mathtex>, где <mathtex>a = 2, b = 2, c = 0</mathtex>

| <mathtex>T(n) = 2 T\left(\fracdfrac{n}{2}\right) + O(n)</mathtex>| <mathtex>O(n \log n)</mathtex>| По мастер-теореме <mathtex>c = \log_b a</mathtex>, где <mathtex>a = 2, b = 2, c = 1</mathtex>

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