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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Формулировка и доказательство мастер-теоремы)
Строка 20: Строка 20:
 
Тогда решение данной рекурренты зависит от соотношения между <tex>a, b, c</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) = O\left( n^{c} \right)</tex>
# Если <tex>c = \log_b a</tex>, то <tex>T(n) = \Theta\left( n^{c} \log n \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) = \Theta\left( n^{\log_b a} \right)</tex>
+
# Если <tex>c < \log_b a</tex>, то <tex>T(n) = O\left( n^{\log_b a} \right)</tex>
  
|proof= Заметим, что <tex> O(1) </tex> не влияет на дальнейшее рассмотрение, т.к. оно учитывается не более чем константное число раз, что не существенно в асимптотике алгоритма. Рассмотрим дерево рекурсии. Всего в нем будет <tex>\log_b n</tex> уровней. На каждом таком уровне, количество подзадач будет умножаться на <tex>a</tex>, так на уровне <tex>i</tex> будет <tex>a^i</tex> подзадач. Также известно, что каждая подзадача на уровне <tex>i</tex> размера <tex>O\left(\dfrac{n}{b^i}\right)</tex>. Подзадача размера <tex>O\left(\left(\dfrac{n}{b^i}\right)\right)</tex> требует <tex>O\left(\left(\dfrac{n}{b^i}\right) ^ c\right)</tex> дополнительных затрат, поэтому общее количество совершенных операций на уровне <tex>i</tex> :   
+
|proof= Заметим, что <tex> O(1) </tex> не влияет на дальнейшее рассмотрение, т.к. оно учитывается не более чем константное число раз, что не существенно в асимптотике алгоритма. Рассмотрим дерево рекурсии. Всего в нем будет <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>\left(\dfrac{n}{b^i}\right) ^ c</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> a^i\left(\dfrac{n}{b^i}\right)^c = n^c\left(\dfrac{a^i}{b^{ic}}\right) = n^c\left(\dfrac{a}{b^c}\right)^i</tex>
 
Заметим, что количество операций увеличивается, уменьшается и остается константой, если <tex>\left(\dfrac{a}{b^c}\right)^i</tex> увеличивается, уменьшается или остается константой соответственно.
 
Заметим, что количество операций увеличивается, уменьшается и остается константой, если <tex>\left(\dfrac{a}{b^c}\right)^i</tex> увеличивается, уменьшается или остается константой соответственно.
  
Строка 31: Строка 31:
  
 
Распишем всю работу в течение рекурсивного спуска:
 
Распишем всю работу в течение рекурсивного спуска:
<tex dpi = "130"> \cdot \displaystyle\sum_{i=1}^{\log_b n}n^c\left(\frac{a}{b^c}\right)^i = O\left(n^c\cdot\displaystyle\sum_{i=1}^{\log_b n}\left(\frac{a}{b^c}\right)^i\right)</tex>
+
<tex dpi = "130"> \displaystyle\sum_{i=0}^{\log_b n}n^c\left(\frac{a}{b^c}\right)^i = n^c\cdot\displaystyle\sum_{i=0}^{\log_b n}\left(\frac{a}{b^c}\right)^i</tex>
 +
 
 
Откуда получаем:
 
Откуда получаем:
  
#<tex>\log_b a < c </tex> <tex>\Rightarrow</tex> <tex>T(n) = \Theta\left( n^{c} \right)</tex> (так как <tex dpi = "130"> \left(\dfrac{a}{b^c}\right)^i</tex> убывающая геометрическая прогрессия)
+
#<tex>\log_b a < c </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>\log_b a = c </tex> <tex>\Rightarrow</tex> <tex dpi = "130"> T(n) = \displaystyle\sum_{i=1}^{\log_b n}n^c\cdot\left(\frac{a}{b^c}\right)^i = </tex> <tex dpi = "130> n^c\cdot\displaystyle\sum_{i=1}^{\log_b n}\left(\frac{a}{b^c}\right)^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>
+
#<tex>\log_b a = c </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>\log_b a > c </tex> <tex>\Rightarrow</tex> <tex dpi = "125"> T(n) = \displaystyle\sum_{i=1}^{\log_b n}n^c\cdot\left(\frac{a}{b^c}\right)^i = n^c\cdot\displaystyle\sum_{i=1}^{\log_b n}\left(\dfrac{a}{b^c}\right)^i =  n^c\cdot\left(\dfrac{a}{b^c}\right)^{\log_b n}</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 = "150"> =  </tex>  <tex dpi = "150">  \Theta\left( n^{\log_b a} \right) </tex>  
+
#<tex>\log_b a > c </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>  
  
 
}}
 
}}
Пусть при решении поставленной задачи, существует алгоритм, который разбивает ее на <tex> a </tex> подзадач,при этом <tex>n</tex> — размер общей задачи, <tex dpi = "125">\dfrac{n}{b}</tex> — размер каждой подзадачи, <tex> n ^ {c} </tex> — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач и <tex>d</tex> — начальная стоимость для данной задачи(при <tex>n = 1</tex>).Тогда мастер-теорема позволяет найти асимптотическое решение рекурренты, возникшей в результате анализа асимптотики данной задачи.
+
Пусть при решении поставленной задачи, существует алгоритм, который разбивает ее на <tex> a </tex> подзадач,при этом <tex>n</tex> — размер общей задачи, <tex dpi = "125">\dfrac{n}{b}</tex> — размер каждой подзадачи, <tex> n ^ {c} </tex> — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач и <tex>O(1)</tex> — начальная стоимость для данной задачи(при <tex>n = 1</tex>).Тогда мастер-теорема позволяет найти асимптотическое решение рекурренты, возникшей в результате анализа асимптотики данной задачи.
  
 
==Примеры==   
 
==Примеры==   
Строка 49: Строка 50:
  
 
<tex> t(x) = \begin{cases}
 
<tex> t(x) = \begin{cases}
   3 \; t\!\left(\dfrac{x}{2}\right) + n\sqrt{n + 1} , &      n > 1\\  
+
   2 \; t\!\left(\dfrac{x}{2}\right) + n\log n  , &      n > 1\\  
 
   1    , &      n = 1  
 
   1    , &      n = 1  
 
\end{cases}
 
\end{cases}
 
</tex>  
 
</tex>  
  
Рассмотрим <tex> f(n) = n\sqrt{n+1} = \Theta(n^{3/2}) </tex> , тогда данное соотношение удовлетворяет случаю <tex> c < \log_b a</tex>, а именно <tex> \dfrac{3}{2} < \log_2 3 </tex>, тогда
+
Заметим, что <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> \Theta(n ^ {\log_2 3}) </tex>.
 
  
 
==== Пример 2 ====
 
==== Пример 2 ====
Строка 70: Строка 70:
 
<tex>f(n) = n\sqrt {n + 1} < n\sqrt{n + n} < n\sqrt{2n} = O(n^{3/2}) </tex>
 
<tex>f(n) = n\sqrt {n + 1} < n\sqrt{n + n} < n\sqrt{2n} = O(n^{3/2}) </tex>
  
Данное соотношение подходит под первый случай <tex>\left(a = 2, b = 3, c = \dfrac{3}{2}\right)</tex>, поэтому его асимптотика совпадает с асимптотикой <tex>f(n)</tex> (следуя из определения <tex> \Theta </tex> и <tex> O </tex>).
+
Данное соотношение подходит под первый случай <tex>\left(a = 2, b = 3, c = \dfrac{3}{2}\right)</tex>, поэтому его асимптотика совпадает с асимптотикой <tex>f(n)</tex>.
 +
 
 
=== Недопустимые соотношения ===
 
=== Недопустимые соотношения ===
Рассмотрим пару ошибочно-составленных соотношений:
+
Рассмотрим пару соотношений, которые нельзя решить мастер-теоремой:
 
*<tex dpi = "130">T(n) = 2^nT\left (\dfrac{n}{2}\right )+n^n</tex>
 
*<tex dpi = "130">T(n) = 2^nT\left (\dfrac{n}{2}\right )+n^n</tex>
 
*:<tex>a</tex> не является константой; количество подзадач может меняться
 
*:<tex>a</tex> не является константой; количество подзадач может меняться
 
*<tex dpi = "130">T(n) = 2T\left (\dfrac{n}{2}\right )+\frac{n}{\log n}</tex>
 
*<tex dpi = "130">T(n) = 2T\left (\dfrac{n}{2}\right )+\frac{n}{\log n}</tex>
*:рассмотрим <tex> f(n) = \dfrac{n}{\log n} </tex> , тогда не существует такого полинома, что <tex> \dfrac{n}{\log n} \in \Theta(n^c) </tex>  
+
*:рассмотрим <tex> f(n) = \dfrac{n}{\log n} </tex> , тогда <tex> f(n)  = O(n^c), c \ge 1 </tex> , тогда <tex> \dfrac{f(n)}{n^1} </tex> не является полиномом какой-либо степени, что противоречит условиям теоремы.
 
*<tex dpi = "130">T(n) = 0.5T\left (\dfrac{n}{2}\right )+n</tex>
 
*<tex dpi = "130">T(n) = 0.5T\left (\dfrac{n}{2}\right )+n</tex>
 
*:<tex>a < 1</tex> не может быть меньше одной подзадачи
 
*:<tex>a < 1</tex> не может быть меньше одной подзадачи
Строка 90: Строка 91:
 
|-
 
|-
 
| [[Целочисленный двоичный поиск]]
 
| [[Целочисленный двоичный поиск]]
| <tex>T(n) = T\left(\frac{n}{2}\right) + O(1)</tex>
+
| <tex>T(n) = T\left(\dfrac{n}{2}\right) + O(1)</tex>
 
| <tex>O(\log n)</tex>
 
| <tex>O(\log n)</tex>
 
| По мастер-теореме <tex>c = \log_b a</tex>, где <tex>a = 1, b = 2, c = 0</tex>
 
| По мастер-теореме <tex>c = \log_b a</tex>, где <tex>a = 1, b = 2, c = 0</tex>
 
|-
 
|-
 
| [[Дерево поиска, наивная реализация | Обход бинарного дерева]]
 
| [[Дерево поиска, наивная реализация | Обход бинарного дерева]]
| <tex>T(n) = 2 T\left(\frac{n}{2}\right) + O(1)</tex>
+
| <tex>T(n) = 2 T\left(\dfrac{n}{2}\right) + O(1)</tex>
 
| <tex>O(n)</tex>
 
| <tex>O(n)</tex>
 
| По мастер-теореме <tex>c < \log_b a</tex>, где <tex>a = 2, b = 2, c = 0</tex>
 
| По мастер-теореме <tex>c < \log_b a</tex>, где <tex>a = 2, b = 2, c = 0</tex>
 
|-
 
|-
 
|  [[Сортировка слиянием]]
 
|  [[Сортировка слиянием]]
| <tex>T(n) = 2 T\left(\frac{n}{2}\right) + O(n)</tex>
+
| <tex>T(n) = 2 T\left(\dfrac{n}{2}\right) + O(n)</tex>
 
| <tex>O(n \log n)</tex>
 
| <tex>O(n \log n)</tex>
 
| По мастер-теореме <tex>c = \log_b a</tex>, где <tex>a = 2, b = 2, c = 1</tex>
 
| По мастер-теореме <tex>c = \log_b a</tex>, где <tex>a = 2, b = 2, c = 1</tex>

Версия 23:50, 10 мая 2015

Мастер теорема (англ. 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].

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

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

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

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

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

Примеры

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

Пример 1

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


[math] t(x) = \begin{cases} 2 \; t\!\left(\dfrac{x}{2}\right) + 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]

Пример 2

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

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

[math] T(n) = \begin{cases} 2 \; T\!\left(\dfrac{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]\left(a = 2, b = 3, c = \dfrac{3}{2}\right)[/math], поэтому его асимптотика совпадает с асимптотикой [math]f(n)[/math].

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

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

  • [math]T(n) = 2^nT\left (\dfrac{n}{2}\right )+n^n[/math]
    [math]a[/math] не является константой; количество подзадач может меняться
  • [math]T(n) = 2T\left (\dfrac{n}{2}\right )+\frac{n}{\log n}[/math]
    рассмотрим [math] f(n) = \dfrac{n}{\log n} [/math] , тогда [math] f(n) = O(n^c), c \ge 1 [/math] , тогда [math] \dfrac{f(n)}{n^1} [/math] не является полиномом какой-либо степени, что противоречит условиям теоремы.
  • [math]T(n) = 0.5T\left (\dfrac{n}{2}\right )+n[/math]
    [math]a \lt 1[/math] не может быть меньше одной подзадачи
  • [math]T(n) = 64T\left (\dfrac{n}{8}\right )-n^2\log n[/math]
    [math]f(n)[/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]


См.также

Примечание

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