Изменения

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

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

<mathtex dpi = "135"> T(n) = \begin{cases}

</mathtex> , где <math>a</math> — количество подзадач, на которые мы разбили разбиваем нашу задачу, <math>n</math> — размер нашей задачи, <mathtex dpi = "145">\frac{n / }{b}</mathtex> — размер подзадачи, <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>a^i(n / b^i)^c = n^c(a^i/b^({ic)}) = n^c(a/b^c)^i</math>Заметим, что количество занятой памяти операций увеличивается, уменьшается и остается константой, если <math>(a/b^c)^i</math> увеличивается, уменьшается или остается константой соответственно.Поэтому мы должны разобрать три случая, когда <math>(a/b^c)^i</math> больше <math>1</math>, равен <math>1 </math> или меньше <math>1</math>.

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

2. <math>\log_b a = c </math> <math>\Rightarrow</math> <tex dpi = "130125"> 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. <math>\log_b a > c </math> <math>\Rightarrow</math> <tex dpi = "130125">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(\frac{a^{log_b n} }{(b^c)^{log_b n}}) </tex> <tex dpi = "130"> = </tex> <tex dpi = "150"> n^c\cdot(\frac{n^{log_b a}}{n^c})</tex> <tex dpi = "130"> = </tex> <tex dpi = "130"> \Theta\left( n^{\log_b a} \right) </tex>

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

<math>f(n) = n\sqrt {n + 1} > n^{3/2} = O(n^{3/2}) </math>, а также <math>f(n) = n\sqrt {n + 1} < n\sqrt{n + n} < n\sqrt{2n} = O(n^{3/2}) </math>

===Недопустимые соотношения===

*:не полиномиальное различие <math>f(n)</math> и <math>n^{\log_b a}</math>, т.к. <tex dpi = "145"> \frac{f(n)}{n^{\log_b a}} < n^r , для любого r > 0</tex>

| Обход бинарного [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>c < \log_b a</math> , где <math>a = 2, b = 2, c = 0</math>

 == Cсылки Источники информации ==