1632
правки
Изменения
м
Теорема|statement=
Пусть у нас дано соотношение вида:
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>.
|proof= Для доказательства мы установим <math>d = 1</math>, это требуется для того, чтобы наши вычисления были хорошо определены при рекурсивном спуске.
Давайте рассмотрим дерево рекурсии. Всего в нем будет <math>\log_b n</math> уровней. На каждом таком уровне, количество подзадач будет умножаться на <math>a</math>, так на уровне <math>i</math> будет <math>a^i</math> подзадач. Также известно, что каждая подзадача на уровне <math>i</math> размера <math>n / b^i</math>. Подзадача размера <math>n / b^i</math> требует <math>(n / b^i) ^ c</math> дополнительных затрат, поэтому общее количество совершенных операций на уровне <math>i</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> больше 1, равен 1 или меньше 1.
Рассмотрим <math>(a/b^c)^i = 1</math> <math>\Leftrightarrow</math> <math>a = b^c</math> <math>\Leftrightarrow</math> <math>\log_b a = c \log_b b</math> <math>\Leftrightarrow</math> <math>\log_b a = c</math>.
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 = "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 </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} </tex> <tex dpi = "130"> = Theta </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>.
}}==Примеры==
Рассчитать для <math>x = 7</math>.
2. Задано такое соотношение:<tex>f(n) =</tex> <tex>n\sqrt{n + 1}</tex>
==Недопустимые соотношения==Рассмотрим пару ошибочно-составленных соотношений:*Данное соотношение подходит под первый случай <mathtex>T(n) = 2^nT\left (\frac{n}{2}\right )+n^n</math>*:<math>a</math> не является константой; количество подзадач может меняться*<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</math>*:не полиномиальное различие <math>f(n)</math> и <math>n^{\log_b a}</math>*<math>T(n) , b = 3, c = 0.5T\left (\fracdfrac{n3}{2}\right )+n</math>*:<math>a</mathtex> , поэтому его асимптотика совпадает с асимптотикой < 1 не может быть меньше одной подзадачи*<mathtex>TO(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math>*:<math>f(n)</math> не положительна*<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math>*:регулярно меняющееся <math>f(n)</mathtex>.
rollbackEdits.php mass rollback
'''Мастер теорема''' — теорема позволяющая (англ. ''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
\end{cases}
, </mathtex> , где <mathtex>a</mathtex> — количество подзадач, на которые мы разбили нашу задачу, <math>n</math> — размер нашей задачи, <math>n / b</math> — размер подзадачи, <math> n ^ {c} </math> — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач, <math>d</math> — единичная стоимость для данной задачи.Пусть <math>a</math> — <mathtex>\in \mathbb N </mathtex> число большее 1, <mathtex>b</mathtex> — <mathtex>\in \mathbb R </mathtex> число большее 1, пусть также <mathtex>c</mathb > — <math>\mathbb R^{+} 1</mathtex> число и , <mathtex>dc</mathtex> — <mathtex>\mathbb \in R^{+} </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> 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
\end{cases}
</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*35/4 + 49/4</math>, тогда <math>t(7) b = 3t(7/2) + 7^2 , \log_b a = 329/21</mathtex>
==== Пример 2 ====
Задано такое соотношение:
<math>f(n) =</math> <math>n\sqrt{n + 1}</math> <mathtex> T(n) = \begin{cases} 2 \; T\!\left(\fracdfrac{n}{3}\right) + O(f(n)) , & n > 1\\
d , & n = 1
\end{cases}
</mathtex>
<mathtex>f(n) = n\sqrt n > n^{3/2} = O(n^{3/2+ 1}) </math>, а также <math>f(n) = n\sqrt n < n\sqrt{n + n} < n\sqrt{2n} = O(n^{3/2}) </mathtex>
=== Недопустимые соотношения ===
Рассмотрим пару соотношений, которые нельзя решить мастер-теоремой:
*<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"
|-
|-
| [[Целочисленный двоичный поиск]]
| <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>
|}
== Cсылки См.также ==* [http://en.wikipedia.org/wiki/Master_theorem Википедия — Мастер-теорема[Амортизационный анализ]* [https://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Dartmouth-university]
== Литература Примечания ==*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<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
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Амортизационный анализ]]
