Изменения

'''Мастер теорема''' (англ. ''Master theorem'') позволяет найти асимптотическое решение рекуррентных соотношений, которые могут возникнуть в анализе асимптотики многих алгоритмов. Однако не все рекуррентные соотношения могут быть решены через мастер теорему, ее обобщения включаются в метод Акра-Бацци.

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

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

1. * Если <mathtex>c > \log_b a</mathtex>, то <mathtex>T(n) = \Theta\left( n^{c} \right)</mathtex>

2. * Если <mathtex>c = \log_b a</mathtex>, то <mathtex>T(n) = \Theta\left( n^{c} \log n \right)</mathtex>

3. * Если <mathtex>c < \log_b a</mathtex>, то <mathtex>T(n) = \Theta\left( n^{\log_b a} \right)</mathtex>

|proof= Для доказательства мы установим <math>d = 1</math>, это требуется для того, чтобы при рекурсивном спуске не возникало огромных вычислений. Давайте рассмотрим дерево рекурсии. Всего в нем будет <mathtex>\log_b n</mathtex> уровней. На каждом таком уровне, количество подзадач будет умножаться на <mathtex>a</mathtex>, так на уровне <mathtex>i</mathtex> будет <mathtex>a^i</mathtex> подзадач. Также известно, что каждая подзадача на уровне <mathtex>i</mathtex> размера <tex dpi = "140">\dfrac{n}{b^i}</tex>. Подзадача размера <tex dpi = "140">\dfrac{n}{b^i}</tex> требует <tex dpi = "140">(\dfrac{n}{b^i}) ^ c</tex> дополнительных затрат, поэтому общее количество совершенных операций на уровне <mathtex>i</mathtex> : <tex dpi = "140">a^i(\dfrac{n}{b^i})^c = n^c(\dfrac{a^i}{b^{ic}}) = n^c(\dfrac{a}{b^c})^i</tex>Заметим, что количество операций увеличивается, уменьшается и остается константой, если <tex dpi = "140">(\dfrac{a}{b^c})^i</tex> увеличивается, уменьшается или остается константой соответственно.Поэтому мы должны разобрать три случая, когда <tex dpi = "132">(\dfrac{a}{b^c})^i</tex> больше <mathtex>1</mathtex>, равен <math>1</math> или меньше <math>1</math>.

<tex dpi = "130"> d\cdot \displaystyle\sum_{i=1}^{\log_b n}n^c(\frac{a}{b^c})^i = n^c\cdot d \cdot\displaystyle\sum_{i=1}^{\log_b n}(\frac{a}{b^c})^i</tex>

1. <mathtex>\log_b a < c </mathtex> <mathtex>\Rightarrow</mathtex> <mathtex>T(n) = \Theta\left( n^{c} \right)</mathtex> (т.к. <tex dpi = "130"> (\dfrac{a}{b^c})^i</tex> убывающая геометрическая прогрессия)

2. <mathtex>\log_b a = c </mathtex> <mathtex>\Rightarrow</mathtex> <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. <mathtex>\log_b a > c </mathtex> <mathtex>\Rightarrow</mathtex> <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(\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>

Рассчитать для <mathtex>x = 7</mathtex>.

<mathtex> t(x) = \begin{cases}

</mathtex>

Заметим, чтобы узнать <mathtex>t(7)</mathtex> , мы должны знать <mathtex>t(7/2)</mathtex>, чтобы узнать <mathtex>t(7/2)</mathtex>, мы должны узнать <mathtex>t(7/4)</mathtex>, <mathtex>1 < 7/4 < 2</mathtex>, тогда <mathtex>t(7/4) = 35/4</mathtex> , <mathtex>t(7/2) = 3\cdot35/4 + 49/4</mathtex>, тогда <mathtex>t(7) = 3t(7/2) + 7^2 = 329/2</mathtex>

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

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

</mathtex>

<mathtex>f(n) = n\sqrt {n + 1} < n\sqrt{n + n} < n\sqrt{2n} = O(n^{3/2}) </mathtex>

Данное соотношение подходит под первый случай <mathtex>(a = 2, b = 3, c = \dfrac{3}{2})</mathtex>, поэтому его асимптотика совпадает с асимптотикой <mathtex>f(n)</mathtex>

*<mathtex dpi = "130">T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</mathtex>*:<mathtex>a</mathtex> не является константой; количество подзадач может меняться*<mathtex dpi = "130">T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</mathtex>*:не полиномиальное различие <math>f(n)</math> и удовлетворяет условию <tex dpi = "140">\dfrac{n^}{\log_b alog n}</tex>, т.к. не равно <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^\epsilonc </tex>, для любого *<tex dpi = "145130">\epsilon > 0</tex>*<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</mathtex>*:<mathtex>a</mathtex> < 1 не может быть меньше одной подзадачи*<mathtex dpi = "130">T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</mathtex>*:<mathtex>f(n)</mathtex> не положительна

| <mathtex>T(n) = T\left(\frac{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(\frac{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(\frac{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>

*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. стр. 110 М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4