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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Источники информации)
Строка 1: Строка 1:
−
'''Мастер теорема''' (Master theorem) теорема позволяющая найти асимптотическое решение рекуррентных соотношений, которые могут возникнуть в реализации многих алгоритмов. Однако не все рекуррентные соотношения могут быть решены через мастер теорему, ее обобщения включаются в метод [http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method Акра-Бацци].
+
'''Мастер теорема''' (англ. Master theorem) позволяет найти асимптотическое решение рекуррентных соотношений, которые могут возникнуть в анализе асимптотики многих алгоритмов. Однако не все рекуррентные соотношения могут быть решены через мастер теорему, ее обобщения включаются в метод Акра-Бацци.
  
 
==Формулировка и доказательство мастер-теоремы==
 
==Формулировка и доказательство мастер-теоремы==
Строка 7: Строка 7:
  
 
<tex dpi = "135"> T(n) = \begin{cases}
 
<tex dpi = "135"> T(n) = \begin{cases}
−
   a \; T\!\left(\frac{n}{b}\right) + n^{c}  , &      n > 1\\  
+
   a \; T\!\left(\dfrac{n}{b}\right) + n^{c}  , &      n > 1\\  
 
   d    , &      n = 1
 
   d    , &      n = 1
 
\end{cases}
 
\end{cases}
 
</tex>  
 
</tex>  
  
−
где <math>a</math> — количество подзадач, на которые мы разбиваем нашу задачу, <math>n</math> — размер нашей задачи, <tex dpi = "145">\frac{n}{b}</tex> — размер подзадачи, <math> n ^ {c} </math> — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач, <math>d</math> — единичная стоимость для данной задачи.
+
где <math>a</math> — количество подзадач, на которые мы разбиваем нашу задачу, <math>n</math> — размер нашей задачи, <tex dpi = "145">\dfrac{n}{b}</tex> — размер подзадачи, <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> , тогда решение данного рекуррентного соотношения разбивается на три возможных случая:
 
Пусть <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> , тогда решение данного рекуррентного соотношения разбивается на три возможных случая:
  
Строка 22: Строка 22:
  
 
|proof= Для доказательства мы установим <math>d = 1</math>, это требуется для того, чтобы при рекурсивном спуске не возникало огромных вычислений.  
 
|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>\log_b n</math> уровней. На каждом таком уровне, количество подзадач будет умножаться на <math>a</math>, так на уровне <math>i</math> будет <math>a^i</math> подзадач. Также известно, что каждая подзадача на уровне <math>i</math> размера <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> дополнительных затрат, поэтому общее количество совершенных операций на уровне <math>i</math> :
−
<math>a^i(n / b^i)^c = n^c(a^i/b^{ic}) = n^c(a/b^c)^i</math>
+
<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>
−
Заметим, что количество операций увеличивается, уменьшается и остается константой, если <math>(a/b^c)^i</math> увеличивается, уменьшается или остается константой соответственно.
+
Заметим, что количество операций увеличивается, уменьшается и остается константой, если <tex dpi = "140">(\dfrac{a}{b^c})^i</tex> увеличивается, уменьшается или остается константой соответственно.
−
Поэтому мы должны разобрать три случая, когда <math>(a/b^c)^i</math> больше <math>1</math>, равен <math>1</math> или меньше <math>1</math>.
+
Поэтому мы должны разобрать три случая, когда <tex dpi = "132">(\dfrac{a}{b^c})^i</tex> больше <math>1</math>, равен <math>1</math> или меньше <math>1</math>.
−
Рассмотрим <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 = "140">(\dfrac{a}{b^c})^i = 1</tex> <tex dpi = "140">\Leftrightarrow a = b^c\Leftrightarrow\ log_b a = c \log_b b\Leftrightarrow\log_b a = c</tex>.
 
Распишем всю работу в течение рекурсивного спуска:
 
Распишем всю работу в течение рекурсивного спуска:
 
<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"> \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>
Строка 42: Строка 42:
  
 
=== Примеры задач ===
 
=== Примеры задач ===
−
 
+
==== Пример 1 ====
−
1.Пусть задано такое рекуррентное соотношение:
+
Пусть задано такое рекуррентное соотношение:
  
 
Рассчитать для <math>x = 7</math>.
 
Рассчитать для <math>x = 7</math>.
Строка 53: Строка 53:
 
</math>  
 
</math>  
  
−
Заметим, чтобы узнать <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>
+
Заметим, чтобы узнать <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\cdot35/4 + 49/4</math>, тогда <math>t(7) = 3t(7/2) + 7^2 = 329/2</math>
  
−
 
+
==== Пример 2 ====
−
2. Задано такое соотношение:
+
Задано такое соотношение:
  
 
<math>f(n) =</math> <math>n\sqrt{n + 1}</math>
 
<math>f(n) =</math> <math>n\sqrt{n + 1}</math>
Строка 66: Строка 66:
 
</math>
 
</math>
  
−
<math>f(n) = n\sqrt {n + 1} > n^{3/2} = O(n^{3/2}) </math>, а также  
+
<tex>f(n) = n\sqrt {n + 1} \ge n\sqrt n = n^{3/2} = O(n^{3/2}) </tex>, а также  
 
<math>f(n) = n\sqrt {n + 1} < n\sqrt{n + n} < n\sqrt{2n} = 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>a = 2, b = 3, c = \dfrac{3}{2}</math>), поэтому его асимптотика совпадает с асимптотикой <math>f(n)</math>
 
=== Недопустимые соотношения ===
 
=== Недопустимые соотношения ===
 
Рассмотрим пару ошибочно-составленных соотношений:
 
Рассмотрим пару ошибочно-составленных соотношений:
Строка 74: Строка 75:
 
*:<math>a</math> не является константой; количество подзадач может меняться
 
*:<math>a</math> не является константой; количество подзадач может меняться
 
*<math>T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}</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>, т.к. <tex dpi = "145"> \frac{f(n)}{n^{\log_b a}} < n^r , для любого r > 0</tex>  
+
*:не полиномиальное различие <math>f(n)</math> и <math>n^{\log_b a}</math>, т.к. <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^\epsilon</tex>, для любого <tex dpi = "145">\epsilon > 0</tex>
 
*<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math>
 
*<math>T(n) = 0.5T\left (\frac{n}{2}\right )+n</math>
 
*:<math>a</math> < 1 не может быть меньше одной подзадачи
 
*:<math>a</math> < 1 не может быть меньше одной подзадачи
 
*<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math>
 
*<math>T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n</math>
 
*:<math>f(n)</math> не положительна
 
*:<math>f(n)</math> не положительна
−
*<math>T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)</math>
+
=== Приложение к известным алгоритмам ===
−
*:регулярно меняющееся <math>f(n)</math>
 
−
 
 
−
 
 
−
== Приложение к известным алгоритмам ==
 
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
Строка 96: Строка 93:
 
| По мастер-теореме <math>c = \log_b a</math>, где <math>a = 1, b = 2, c = 0</math>
 
| По мастер-теореме <math>c = \log_b a</math>, где <math>a = 1, b = 2, c = 0</math>
 
|-
 
|-
−
| Обход [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>T(n) = 2 T\left(\frac{n}{2}\right) + O(1)</math>
 
| <math>T(n) = 2 T\left(\frac{n}{2}\right) + O(1)</math>
 
| <math>O(n)</math>
 
| <math>O(n)</math>
Строка 112: Строка 109:
 
* [https://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Dartmouth university — the master theorem]
 
* [https://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Dartmouth university — the master theorem]
 
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4
 
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4
 +
 +
== Примечание ==
 +
[http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method Метод Акра-Бацци.]
  
 
== См.также ==
 
== См.также ==

Версия 00:58, 7 мая 2015

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

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

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

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

где [math]a[/math] — количество подзадач, на которые мы разбиваем нашу задачу, [math]n[/math] — размер нашей задачи, [math]\dfrac{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] , тогда решение данного рекуррентного соотношения разбивается на три возможных случая:

1. Если [math]c \gt \log_b a[/math], то [math]T(n) = \Theta\left( n^{c} \right)[/math]

2. Если [math]c = \log_b a[/math], то [math]T(n) = \Theta\left( n^{c} \log n \right)[/math]

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

Для доказательства мы установим [math]d = 1[/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]\dfrac{n}{b^i}[/math] требует [math](\dfrac{n}{b^i}) ^ c[/math] дополнительных затрат, поэтому общее количество совершенных операций на уровне [math]i[/math] : [math]a^i(\dfrac{n}{b^i})^c = n^c(\dfrac{a^i}{b^{ic}}) = n^c(\dfrac{a}{b^c})^i[/math] Заметим, что количество операций увеличивается, уменьшается и остается константой, если [math](\dfrac{a}{b^c})^i[/math] увеличивается, уменьшается или остается константой соответственно. Поэтому мы должны разобрать три случая, когда [math](\dfrac{a}{b^c})^i[/math] больше [math]1[/math], равен [math]1[/math] или меньше [math]1[/math]. Рассмотрим [math](\dfrac{a}{b^c})^i = 1[/math] [math]\Leftrightarrow a = b^c\Leftrightarrow\ log_b a = c \log_b b\Leftrightarrow\log_b a = c[/math]. Распишем всю работу в течение рекурсивного спуска: [math] \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[/math] Откуда получаем:

1. [math]\log_b a \lt c [/math] [math]\Rightarrow[/math] [math]T(n) = \Theta\left( n^{c} \right)[/math] (т.к. [math] (\frac{a}{b^c})^i[/math] убывающая геометрическая прогрессия)

2. [math]\log_b a = c [/math] [math]\Rightarrow[/math] [math] T(n) = \displaystyle\sum_{i=1}^{\log_b n}n^c\cdot(\frac{a}{b^c})^i = [/math] [math] 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) [/math]

3. [math]\log_b a \gt c [/math] [math]\Rightarrow[/math] [math] 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)[/math], но [math] n^c\cdot(\frac{a}{b^c})^{log_b n} [/math] [math] = [/math] [math] n^c\cdot(\frac{a^{log_b n} }{(b^c)^{log_b n}}) [/math] [math] = [/math] [math] n^c\cdot(\frac{n^{log_b a}}{n^c})[/math] [math] = [/math] [math] \Theta\left( n^{\log_b a} \right) [/math]
[math]\triangleleft[/math]

Примеры

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

Пример 1

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

Рассчитать для [math]x = 7[/math].

[math] t(x) = \begin{cases} 3 \; t\!\left(\frac{x}{2}\right) + x^{2} , & x \gt 2\\ 5x , & 1 \lt x \lt 2 \end{cases} [/math]

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

Пример 2

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

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

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

[math]f(n) = n\sqrt {n + 1} \ge n\sqrt n = n^{3/2} = O(n^{3/2}) [/math], а также [math]f(n) = n\sqrt {n + 1} \lt n\sqrt{n + n} \lt n\sqrt{2n} = O(n^{3/2}) [/math]

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

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

Рассмотрим пару ошибочно-составленных соотношений:

  • [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]\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} \lt n^\epsilon[/math], для любого [math]\epsilon \gt 0[/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) + 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(\frac{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(\frac{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]


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

Примечание

Метод Акра-Бацци.

См.также

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Мастер-теорема&oldid=46088»