59
правок
Изменения
Новая страница: «'''Мастер теорема''' — теорема позволяющая найти асимптотическое решение (с помощью [https://r...»
'''Мастер теорема''' — теорема позволяющая найти асимптотическое решение (с помощью [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 О - большое нотации]) рекуррентных соотношений, которые могут возникнуть во многих алгоритмах, например таких как разделяй и властвуй. Однако не все рекуррентные соотношения могут быть решены через мастер теорему, ее обобщения включаются в метод Акра-Бацци.
==Формулировка и доказательство мастер-теоремы==
{{
Теорема|statement=
Пусть у нас дано соотношение вида:
<math> T(n) = \begin{cases}
a \; T\!\left(\frac{n}{b}\right) + n^{c} , & n > 1\\
d , & n = 1
\end{cases}
</math>
, где <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> , тогда возможны три случая:
1. Если <math>c > \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 < \log_b a</math>, то <math>T(n) = \Theta\left( n^{\log_b a} \right)</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>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>
Откуда получаем:
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> убывающая геометрическая прогрессия)
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>
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>
}}
==Примеры==
Пусть у нас задана такое рекуррентное соотношение:
<math> t(x) = \begin{cases}
3 \; t\!\left(\frac{x}{2}\right) + x^{2} , & x > 2\\
5x , & 1 < x < 2
\end{cases}
</math>
Рассчитать для <math>x = 7</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(n) = \begin{cases}
2 \; t\!\left(\n\right) + f(n) , & n > 1\\
d , & n = 1
\end{cases}
</math>
==Формулировка и доказательство мастер-теоремы==
{{
Теорема|statement=
Пусть у нас дано соотношение вида:
<math> T(n) = \begin{cases}
a \; T\!\left(\frac{n}{b}\right) + n^{c} , & n > 1\\
d , & n = 1
\end{cases}
</math>
, где <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> , тогда возможны три случая:
1. Если <math>c > \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 < \log_b a</math>, то <math>T(n) = \Theta\left( n^{\log_b a} \right)</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>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>
Откуда получаем:
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> убывающая геометрическая прогрессия)
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>
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>
}}
==Примеры==
Пусть у нас задана такое рекуррентное соотношение:
<math> t(x) = \begin{cases}
3 \; t\!\left(\frac{x}{2}\right) + x^{2} , & x > 2\\
5x , & 1 < x < 2
\end{cases}
</math>
Рассчитать для <math>x = 7</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(n) = \begin{cases}
2 \; t\!\left(\n\right) + f(n) , & n > 1\\
d , & n = 1
\end{cases}
</math>
