Изменения

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

В анализе асимптотики алгоритма получено соотношение такого видаПусть имеется рекуррентное соотношения:

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

где <tex>a</tex> — количество подзадач, на которые мы разбиваем нашу задачу, <tex>n</tex> — размер нашей задачи, <tex dpi = "125">\dfrac{n}{b}</tex> — размер подзадачи, <tex> n ^ {c} </tex> — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач, <math>d</math> — начальная стоимость для данной задачи(при <math>n = 1</math>).Пусть <tex>a</tex> — <tex>\mathbb N </tex> число большее <tex>1</tex>, <tex>b</tex> — <tex>\mathbb R </tex> число большее <tex>1</tex>, <tex>c</tex> — <tex>\mathbb R^{+} </tex> число и <tex>d</tex> — <tex>\mathbb R^{+} </tex> , тогда Тогда асимптотическое решение данной рекурренты зависит от соотношения между <tex>a, b, c</tex> такимеет вид:

* # Если <tex>c > \log_b a</tex>, то <tex>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)</tex>

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

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

<tex dpi = "130"> d\cdot 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 d \cdot\displaystyle\sum_{i=10}^{\log_b n}\left(\frac{a}{b^c}\right)^i\right)</tex> 

1. #<tex>c >\log_b a < c </tex> <tex>\Rightarrow</tex> <tex>T(n) = \ThetaO\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>

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

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

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

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

Данное соотношение подходит под первый случай <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 (\fracdfrac{n}{2}\right )+O(n^n)</tex>*:<tex>a</tex> не является константой; количество подзадач может меняться,*<tex dpi = "130">T(n) = 2T\left (\fracdfrac{n}{2}\right )+O\fracleft(\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 (\fracdfrac{n}{2}\right )+O(n)</tex>*:<tex>|a| < 1</tex> , однако пример можно решить следующим образом: заметим, что на < 1 не может быть меньше одной подзадачи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) = 64T-2T\left (\fracdfrac{n}{83}\right )-+O(n^2\log n)</tex>*:<tex>f(n)a < 0 </tex>, при составлении асимптотического решения перед <tex> O </tex> не положительнакаждый раз будет новый знак, что противоречит мастер-теореме. 

| <tex>T(n) = T\left(\fracdfrac{n}{2}\right) + O(1)</tex>

| <tex>T(n) = 2 T\left(\fracdfrac{n}{2}\right) + O(1)</tex>

| <tex>T(n) = 2 T\left(\fracdfrac{n}{2}\right) + O(n)</tex>