Мастер-теорема — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 49 промежуточных версий 5 участников)
Строка 1: Строка 1:
'''Мастер теорема''' — теорема позволяющая найти асимптотическое решение (с помощью [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 О - большое нотации]) рекуррентных соотношений, которые могут возникнуть во многих алгоритмах, например таких как разделяй и властвуй. Однако не все рекуррентные соотношения могут быть решены через мастер теорему, ее обобщения включаются в метод Акра-Бацци.
+
'''Мастер теорема''' (англ. ''Master theorem'') позволяет найти асимптотическое решение рекуррентных соотношений, которые могут возникнуть в анализе асимптотики многих алгоритмов. Однако не все рекуррентные соотношения могут быть решены через мастер теорему, ее обобщения включаются в метод Акра-Бацци<ref>[http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method Википедия {{---}} Метод Акра-Бацци]</ref>.
  
 
==Формулировка и доказательство мастер-теоремы==
 
==Формулировка и доказательство мастер-теоремы==
 
{{
 
{{
Теорема|statement=
 
Пусть у нас дано соотношение вида:
 
  
<math> T(n) = \begin{cases}
+
Теорема
   a \; T\!\left(\frac{n}{b}\right) + n^{c}  , &      n > 1\\  
+
|about =
   d   , &      n = 1
+
мастер-теорема
 +
|statement=
 +
Пусть имеется рекуррентное соотношения:
 +
 
 +
<tex dpi = "135"> T(n) = \begin{cases}
 +
   a \; T\!\left(\dfrac{n}{b}\right) + O(n^{c}) , &      n > 1\\  
 +
   O(1)   , &      n = 1
 
\end{cases}
 
\end{cases}
</math>  
+
, </tex>
, где <math>a</math> — количество подзадач, на которые мы разбили нашу задачу, <math>n</math> — размер нашей задачи, <math>n / b</math> — размер подзадачи, <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> , тогда возможны три случая:
+
где <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>.
 +
 
 +
Тогда асимптотическое решение имеет вид:
  
1. Если <math>c > \log_b a</math>, то <math>T(n) = \Theta\left( n^{c} \right)</math>
+
# Если <tex>c > \log_b a</tex>, то <tex>T(n) = O\left( 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>
  
2. Если <math>c = \log_b a</math>, то <math>T(n) = \Theta\left( n^{c} \log n \right)</math>
+
|proof= Рассмотрим дерево рекурсии данного соотношения. Всего в нем будет <tex>\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> O\left(a^i\left(\dfrac{n}{b^i}\right)^c\right) = O\left (n^c\left(\dfrac{a^i}{b^{ic}}\right)\right) = O\left (n^c\left(\dfrac{a}{b^c}\right)^i\right)</tex>
 +
Заметим, что количество операций увеличивается, уменьшается и остается константой, если <tex>\left(\dfrac{a}{b^c}\right)^i</tex> увеличивается, уменьшается или остается константой соответственно.
  
3. Если <math>c < \log_b a</math>, то <math>T(n) = \Theta\left( n^{\log_b a} \right)</math>
+
Поэтому решение разбивается на три случая, когда <tex>\dfrac{a}{b^c}</tex> больше <tex>1</tex>, равна <math>1</math> или меньше <math>1</math>.  Рассмотрим <tex dpi = "130">\dfrac{a}{b^c}\ = 1\Leftrightarrow a = b^c \Leftrightarrow\ \log_b a = c \log_b b \Leftrightarrow\ \log_b a = c</tex>.
  
|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>.
 
 
Распишем всю работу в течение рекурсивного спуска:
 
Распишем всю работу в течение рекурсивного спуска:
<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>
+
<tex dpi = "130">T(n) = \displaystyle\sum_{i=0}^{\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=0}^{\log_b n}\left(\frac{a}{b^c}\right)^i\right)</tex>
 +
 
 
Откуда получаем:
 
Откуда получаем:
  
1. <math>\log_b a < c \log_b b</math> <math>\Rightarrow</math> <math>T(n) = \Theta\left( n^{c} \right)</math> (т.к. <tex dpi = "130"> (\frac{a}{b^c})^i</tex> убывающая геометрическая прогрессия)
+
#<tex>c > \log_b a  </tex> <tex>\Rightarrow</tex> <tex>T(n) = O\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. <math>\log_b a = c \log_b b</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 = 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>
+
}}
 +
Мастер-теорема имеет прямое отношение к анализу алгоритмов, так как рекуррентное соотношение можно воспринимать следующим образом: имеется задача размера <tex> n </tex>, алгоритм разбивает её на <tex> a </tex> подзадач размера <tex> \dfrac{n}{b} </tex> , тратит дополнительно <tex> O(n^c) </tex>  действий, а если размер подзадачи становится равен единице, то алгоритму требуется <tex>O(1)</tex> действий на её решение.
  
3. <math>\log_b a > c \log_b b</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)</tex>, но  <tex dpi = "150"> n^c(\frac{a}{b^c})^{log_b n} </tex> <tex dpi = "130"> =  </tex>  <tex dpi = "150">  n^c(\frac{a^{log_b n} }{(b^c)^{log_b n}})  </tex> <tex dpi = "130"> =  </tex> <tex dpi = "150"> n^c(\frac{n^{log_b a}}{n^c})</tex> <tex dpi = "130"> =  </tex> <tex dpi = "130">   \Theta\left( n^{\log_b a} \right) </tex>
+
Из доказательства теоремы видно, что если в рекурретном соотношении заменить <tex> O </tex> на <tex> \Theta </tex> и <tex> \Omega </tex>, то и асимптотика решения изменится соответствующим образом на <tex> \Theta </tex> или <tex> \Omega </tex>.
  
}}
+
==Примеры== 
  
==Примеры==
+
=== Примеры задач ===
1.Пусть у нас задано такое рекуррентное соотношение:
+
==== Пример 1 ====
 +
Пусть задано такое рекуррентное соотношение:
  
Рассчитать для <math>x = 7</math>.
 
  
<math> t(x) = \begin{cases}
+
<tex> t(n) = \begin{cases}
   3 \; t\!\left(\frac{x}{2}\right) + x^{2} , &      x > 2\\  
+
   2 \; t\!\left(\dfrac{n}{2}\right) + O(n\log n) , &      n > 1\\  
   5x   , &      1 < x < 2
+
   1   , &      n = 1  
 
\end{cases}
 
\end{cases}
</math>  
+
</tex>  
  
Заметим, чтобы узнать <math>t(7)</math> , мы должны знать <math>t(7/2)</math>, чтобы узнать <math>t(7/2)</math>, мы должны узнать <math>t(7/4)</math>, <math>1 < 7/4 < 2</math>, тогда <math>t(7/4) = 35/4</math> , <math>t(7/2) = 3*35/4 + 49/4</math>, тогда <math>t(7) = 3t(7/2) + 7^2 = 329/2</math>
+
Заметим, что <tex> n\log n = O(n^c) </tex>, для любого <tex> c > 1 </tex>, что удовлетворяет 1 условию. Тогда <tex> T(n) = O(n^c) </tex>, где <tex> c > 1 </tex>, при <tex> a = 2, b = 2, \log_b a = 1</tex>
  
 +
==== Пример 2 ====
 +
Задано такое соотношение:
  
2. Задано такое соотношение:
+
<tex>f(n) =</tex> <tex>n\sqrt{n + 1}</tex>
  
<math>f(n) =</math> <math>n\sqrt{n + 1}</math>
+
<tex> T(n) = \begin{cases}
 
+
   2 \; T\!\left(\dfrac{n}{3}\right) + O(f(n))  , &      n > 1\\  
<math> T(n) = \begin{cases}
 
   2 \; T\!\left(\frac{n}{3}\right) + f(n)  , &      n > 1\\  
 
 
   d    , &      n = 1  
 
   d    , &      n = 1  
 
\end{cases}
 
\end{cases}
</math>
+
</tex>
  
<math>f(n) = n\sqrt n > n^{3/2} = O(n^{3/2}) </math>, а также
+
<tex>f(n) = n\sqrt {n + 1} < n\sqrt{n + n} < n\sqrt{2n} = O(n^{3/2}) </tex>
<math>f(n) = n\sqrt n < n\sqrt{n + n} < n\sqrt{2n} = O(n^{3/2}) </math>
 
  
==Недопустимые соотношения==
+
Данное соотношение подходит под первый случай <tex>\left(a = 2, b = 3, c = \dfrac{3}{2}\right)</tex>, поэтому его асимптотика совпадает с асимптотикой <tex>O(f(n))</tex>.
Рассмотрим пару ошибочно-составленных соотношений:
 
*<math>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) = 0.5T\left (\frac{n}{2}\right )+n</math>
 
*:<math>a</math> < 1 не может быть меньше одной подзадачи
 
*<math>T(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)</math>
 
  
 +
=== Недопустимые соотношения ===
 +
Рассмотрим пару соотношений, которые нельзя решить мастер-теоремой:
 +
*<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"
 
{| class="wikitable"
 
|-
 
|-
Строка 88: Строка 94:
 
|-
 
|-
 
| [[Целочисленный двоичный поиск]]
 
| [[Целочисленный двоичный поиск]]
| <math>T(n) = T\left(\frac{n}{2}\right) + O(1)</math>
+
| <tex>T(n) = T\left(\dfrac{n}{2}\right) + O(1)</tex>
| <math>O(\log n)</math>
+
| <tex>O(\log n)</tex>
| По мастер-теореме <math>c = \log_b a</math>, где <math>a = 1, b = 2, c = 0</math>
+
| По мастер-теореме <tex>c = \log_b a</tex>, где <tex>a = 1, b = 2, c = 0</tex>
 
|-
 
|-
| Обход бинарного дерева
+
| [[Дерево поиска, наивная реализация | Обход бинарного дерева]]
| <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(1)</math>
+
| <tex>T(n) = 2 T\left(\dfrac{n}{2}\right) + O(1)</tex>
| <math>O(n)</math>
+
| <tex>O(n)</tex>
| По мастер-теореме <math>c < \log_b a</math> где <math>a = 2, b = 2, c = 0</math>
+
| По мастер-теореме <tex>c < \log_b a</tex>, где <tex>a = 2, b = 2, c = 0</tex>
 
|-
 
|-
 
|  [[Сортировка слиянием]]
 
|  [[Сортировка слиянием]]
| <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(n)</math>
+
| <tex>T(n) = 2 T\left(\dfrac{n}{2}\right) + O(n)</tex>
| <math>O(n \log n)</math>
+
| <tex>O(n \log n)</tex>
| По мастер-теореме <math>c = \log_b a</math>, где <math>a = 2, b = 2, c = 1</math>
+
| По мастер-теореме <tex>c = \log_b a</tex>, где <tex>a = 2, b = 2, c = 1</tex>
 
|}
 
|}
  
== Cсылки ==
+
== См.также ==
* [http://en.wikipedia.org/wiki/Master_theorem Википедия — Мастер-теорема]
+
* [[Амортизационный анализ]]
* [https://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf]
 
  
== Литература ==
+
== Примечания ==
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 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
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Амортизационный анализ]]
 
[[Категория:Амортизационный анализ]]

Текущая версия на 19:37, 4 сентября 2022

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

Формулировка и доказательство мастер-теоремы

Теорема (мастер-теорема):
Пусть имеется рекуррентное соотношения:

[math] T(n) = \begin{cases} a \; T\!\left(\dfrac{n}{b}\right) + O(n^{c}) , & n \gt 1\\ O(1) , & n = 1 \end{cases} , [/math]

где [math]a[/math] [math]\in \mathbb N [/math], [math]b[/math] [math] \in \mathbb R [/math], [math] b \gt 1[/math], [math]c[/math] [math]\mathbb \in R^{+} [/math].

Тогда асимптотическое решение имеет вид:

  1. Если [math]c \gt \log_b a[/math], то [math]T(n) = O\left( n^{c} \right)[/math]
  2. Если [math]c = \log_b a[/math], то [math]T(n) = O\left( n^{c} \log n \right)[/math]
  3. Если [math]c \lt \log_b a[/math], то [math]T(n) = O\left( n^{\log_b a} \right)[/math]
Доказательство:
[math]\triangleright[/math]

Рассмотрим дерево рекурсии данного соотношения. Всего в нем будет [math]\log_b n[/math] уровней. На каждом таком уровне, количество детей в дереве будет умножаться на [math]a[/math], так на уровне [math]i[/math] будет [math]a^i[/math] детей. Также известно, что каждый ребенок на уровне [math]i[/math] размера [math]\dfrac{n}{b^i}[/math]. Ребенок размера [math]\left(\dfrac{n}{b^i}\right)[/math] требует [math]O\left(\left(\dfrac{n}{b^i}\right) ^ c\right)[/math] дополнительных затрат, поэтому общее количество совершенных действий на уровне [math]i[/math] : [math] O\left(a^i\left(\dfrac{n}{b^i}\right)^c\right) = O\left (n^c\left(\dfrac{a^i}{b^{ic}}\right)\right) = O\left (n^c\left(\dfrac{a}{b^c}\right)^i\right)[/math] Заметим, что количество операций увеличивается, уменьшается и остается константой, если [math]\left(\dfrac{a}{b^c}\right)^i[/math] увеличивается, уменьшается или остается константой соответственно.

Поэтому решение разбивается на три случая, когда [math]\dfrac{a}{b^c}[/math] больше [math]1[/math], равна [math]1[/math] или меньше [math]1[/math]. Рассмотрим [math]\dfrac{a}{b^c}\ = 1\Leftrightarrow a = b^c \Leftrightarrow\ \log_b a = c \log_b b \Leftrightarrow\ \log_b a = c[/math].

Распишем всю работу в течение рекурсивного спуска: [math]T(n) = \displaystyle\sum_{i=0}^{\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=0}^{\log_b n}\left(\frac{a}{b^c}\right)^i\right)[/math]

Откуда получаем:

  1. [math]c \gt \log_b a [/math] [math]\Rightarrow[/math] [math]T(n) = O\left( n^{c} \right)[/math] (так как [math] \left(\dfrac{a}{b^c}\right)^i[/math] убывающая геометрическая прогрессия)
  2. [math]c = \log_b a [/math] [math]\Rightarrow[/math] [math] T(n) = \displaystyle\sum_{i=0}^{\log_b n}n^c\cdot\left(\frac{a}{b^c}\right)^i = [/math] [math] 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) [/math]
  3. [math]c \lt \log_b a [/math] [math]\Rightarrow[/math] [math] 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)[/math], но [math] n^c\cdot\left(\dfrac{a}{b^c}\right)^{\log_b n} [/math] [math] = [/math] [math] n^c\cdot\left(\dfrac{a^{\log_b n} }{(b^c)^{\log_b n}}\right) [/math] [math] = [/math] [math] n^c\cdot\left(\dfrac{n^{\log_b a}}{n^c}\right)[/math] [math] = [/math] [math] n^{\log_b a} \Rightarrow T(n) = O\left(n^{\log_b a}\right)[/math]
[math]\triangleleft[/math]

Мастер-теорема имеет прямое отношение к анализу алгоритмов, так как рекуррентное соотношение можно воспринимать следующим образом: имеется задача размера [math] n [/math], алгоритм разбивает её на [math] a [/math] подзадач размера [math] \dfrac{n}{b} [/math] , тратит дополнительно [math] O(n^c) [/math] действий, а если размер подзадачи становится равен единице, то алгоритму требуется [math]O(1)[/math] действий на её решение.

Из доказательства теоремы видно, что если в рекурретном соотношении заменить [math] O [/math] на [math] \Theta [/math] и [math] \Omega [/math], то и асимптотика решения изменится соответствующим образом на [math] \Theta [/math] или [math] \Omega [/math].

Примеры

Примеры задач

Пример 1

Пусть задано такое рекуррентное соотношение:


[math] t(n) = \begin{cases} 2 \; t\!\left(\dfrac{n}{2}\right) + O(n\log n) , & n \gt 1\\ 1 , & n = 1 \end{cases} [/math]

Заметим, что [math] n\log n = O(n^c) [/math], для любого [math] c \gt 1 [/math], что удовлетворяет 1 условию. Тогда [math] T(n) = O(n^c) [/math], где [math] c \gt 1 [/math], при [math] a = 2, b = 2, \log_b a = 1[/math]

Пример 2

Задано такое соотношение:

[math]f(n) =[/math] [math]n\sqrt{n + 1}[/math]

[math] T(n) = \begin{cases} 2 \; T\!\left(\dfrac{n}{3}\right) + O(f(n)) , & n \gt 1\\ d , & n = 1 \end{cases} [/math]

[math]f(n) = n\sqrt {n + 1} \lt n\sqrt{n + n} \lt n\sqrt{2n} = O(n^{3/2}) [/math]

Данное соотношение подходит под первый случай [math]\left(a = 2, b = 3, c = \dfrac{3}{2}\right)[/math], поэтому его асимптотика совпадает с асимптотикой [math]O(f(n))[/math].

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

Рассмотрим пару соотношений, которые нельзя решить мастер-теоремой:

  • [math]T(n) = 2^nT\left (\dfrac{n}{2}\right )+O(n^n)[/math]
    [math]a[/math] не является константой; количество подзадач может меняться,
  • [math]T(n) = 2T\left (\dfrac{n}{2}\right )+O\left(\dfrac{n}{\log n}\right)[/math]
    рассмотрим [math] f(n) = \dfrac{n}{\log n} [/math] , тогда не существует такого [math] O(n^c) [/math], что [math] f(n) \in O(n^c) [/math], так как при [math] n = 1 , f(n) \rightarrow \!\, \infty [/math], а [math] O(n^c) [/math] ограничено,
  • [math]T(n) = 0.5T\left (\dfrac{n}{2}\right )+O(n)[/math]
    [math]|a| \lt 1[/math], однако пример можно решить следующим образом: заметим, что на [math] i [/math] шаге, размер [math] T(i) \leqslant \dfrac{c \cdot n}{4^i} [/math] , тогда, оценивая сумму, получаем, что [math] T(n) = O(n) [/math],
  • [math]T(n) = -2T\left (\dfrac{n}{3}\right )+O(n^2)[/math]
    [math] a \lt 0 [/math], при составлении асимптотического решения перед [math] O [/math] каждый раз будет новый знак, что противоречит мастер-теореме.

Приложение к известным алгоритмам

Алгоритм Рекуррентное соотношение Время работы Комментарий
Целочисленный двоичный поиск [math]T(n) = T\left(\dfrac{n}{2}\right) + O(1)[/math] [math]O(\log n)[/math] По мастер-теореме [math]c = \log_b a[/math], где [math]a = 1, b = 2, c = 0[/math]
Обход бинарного дерева [math]T(n) = 2 T\left(\dfrac{n}{2}\right) + O(1)[/math] [math]O(n)[/math] По мастер-теореме [math]c \lt \log_b a[/math], где [math]a = 2, b = 2, c = 0[/math]
Сортировка слиянием [math]T(n) = 2 T\left(\dfrac{n}{2}\right) + O(n)[/math] [math]O(n \log n)[/math] По мастер-теореме [math]c = \log_b a[/math], где [math]a = 2, b = 2, c = 1[/math]

См.также

Примечания

Источники информации