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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 17: Строка 17:
 
</tex>  
 
</tex>  
  
, тогда решение данной рекурренты зависит от соотношения между <tex>a, b, c</tex> так:
+
,где  <tex>a</tex> — <tex>\mathbb N </tex> число большее <tex>1</tex>,  <tex>b</tex> — <tex>\mathbb R </tex> число большее <tex>1</tex>, <tex>c</tex> — <tex>\mathbb R^{+} </tex> число и <tex>d</tex> — <tex>\mathbb R^{+} </tex>.
 +
 
 +
Тогда решение данной рекурренты зависит от соотношения между <tex>a, b, c</tex> так:
  
 
* Если <tex>c > \log_b a</tex>, то <tex>T(n) = \Theta\left( n^{c} \right)</tex>
 
* Если <tex>c > \log_b a</tex>, то <tex>T(n) = \Theta\left( n^{c} \right)</tex>
Строка 40: Строка 42:
 
3. <tex>\log_b a > c </tex> <tex>\Rightarrow</tex> <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>  
 
3. <tex>\log_b a > c </tex> <tex>\Rightarrow</tex> <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>  
  
Пусть при решении поставленной задачи, существует алгоритм, который разбивает ее на <tex> a </tex> подзадач,при этом <tex>n</tex> — размер общей задачи, <tex dpi = "125">\dfrac{n}{b}</tex> — размер каждой подзадачи, <tex> n ^ {c} </tex> — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач и <math>d</math> — начальная стоимость для данной задачи(при <tex>n = 1</tex>).
+
Пусть при решении поставленной задачи, существует алгоритм, который разбивает ее на <tex> a </tex> подзадач,при этом <tex>n</tex> — размер общей задачи, <tex dpi = "125">\dfrac{n}{b}</tex> — размер каждой подзадачи, <tex> n ^ {c} </tex> — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач и <math>d</math> — начальная стоимость для данной задачи(при <tex>n = 1</tex>).Тогда мастер-теорема позволяет найти асимптотическое решение рекурренты, возникшей в результате анализа асимптотики данной задачи.
Где  <tex>a</tex> — <tex>\mathbb N </tex> число большее <tex>1</tex>,  <tex>b</tex> — <tex>\mathbb R </tex> число большее <tex>1</tex>, <tex>c</tex> — <tex>\mathbb R^{+} </tex> число и <tex>d</tex> — <tex>\mathbb R^{+} </tex>.Тогда мастер-теорема позволяет найти асимптотическое решение рекурренты, возникшей в результате анализа асимптотики данной задачи.
 
 
}}
 
}}
  

Версия 23:07, 7 мая 2015

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


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

Теорема (Об асимптотическом решении рекуррентного соотношения):
В анализе асимптотики алгоритма получено соотношение такого вида:

[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]\mathbb N [/math] число большее [math]1[/math], [math]b[/math][math]\mathbb R [/math] число большее [math]1[/math], [math]c[/math][math]\mathbb R^{+} [/math] число и [math]d[/math][math]\mathbb R^{+} [/math].

Тогда решение данной рекурренты зависит от соотношения между [math]a, b, c[/math] так:

  • Если [math]c \gt \log_b a[/math], то [math]T(n) = \Theta\left( n^{c} \right)[/math]
  • Если [math]c = \log_b a[/math], то [math]T(n) = \Theta\left( n^{c} \log n \right)[/math]
  • Если [math]c \lt \log_b a[/math], то [math]T(n) = \Theta\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]\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] 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[/math] Откуда получаем:

1. [math]\log_b a \lt c [/math] [math]\Rightarrow[/math] [math]T(n) = \Theta\left( n^{c} \right)[/math] (т.к. [math] (\dfrac{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] a [/math] подзадач,при этом [math]n[/math] — размер общей задачи, [math]\dfrac{n}{b}[/math] — размер каждой подзадачи, [math] n ^ {c} [/math] — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач и [math]d[/math] — начальная стоимость для данной задачи(при [math]n = 1[/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(\dfrac{7}{2})[/math], чтобы узнать [math]t(\dfrac{7}{2})[/math], мы должны узнать [math]t(\dfrac{7}{4})[/math], [math]1 \lt \dfrac{7}{4} \lt 2[/math], тогда [math]t(\dfrac{7}{4}) = \dfrac{35}{4}[/math] , [math]t(\dfrac{7}{2}) = 3\cdot\dfrac{35}{4} + \dfrac{49}{4}[/math], тогда [math]t(7) = 3t(\dfrac{7}{2}) + 7^2 = \dfrac{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} \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] \dfrac{n}{\log n} [/math] не равно [math] n^c [/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]


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

Примечание

См.также