Изменения

В анализе асимптотики алгоритма получено соотношение такого видаПусть имеется рекуррентное соотношения:

a \; T\!\left(\dfrac{n}{b}\right) + O(n^{c} ) , & n > 1\\ d O(1) , & n = 1

, </tex>

,где <tex>a</tex> — <tex>\in \mathbb N </tex> число большее <tex>1</tex>, <tex>b</tex> — <tex>\in \mathbb R </tex> число большее , <tex> b >1</tex>, <tex>c</tex> — <tex>\mathbb R^{+} </tex> число и <tex>d</tex> — <tex>\mathbb in R^{+} </tex>.

Тогда асимптотическое решение данной рекурренты зависит от соотношения между <tex>a, b, c</tex> такимеет вид:

# Если <tex>c > \log_b a</tex>, то <tex>T(n) = \ThetaO\left( n^{c} \right)</tex># Если <tex>c = \log_b a</tex>, то <tex>T(n) = \ThetaO\left( n^{c} \log n \right)</tex># Если <tex>c < \log_b a</tex>, то <tex>T(n) = \ThetaO\left( n^{\log_b a} \right)</tex>

|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> больше <tex>1</tex>, равен равна <math>1</math> или меньше <math>1</math>. Рассмотрим <tex dpi = "140130">\left(\dfrac{a}{b^c}\right)^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"> d\cdot T(n) = \displaystyle\sum_{i=10}^{\log_b n}O\left(n^c\cdot\left(\frac{a}{b^c}\right)^i \right) + O(1)= O\left(n^c\cdot d \cdot\displaystyle\sum_{i=10}^{\log_b n}\left(\frac{a}{b^c}\right)^i\right)</tex> 

#<tex>c >\log_b a < c </tex> <tex>\Rightarrow</tex> <tex>T(n) = \ThetaO\left( n^{c} \right)</tex> (так как <tex dpi = "130"> \left(\dfrac{a}{b^c}\right)^i</tex> убывающая геометрическая прогрессия)#<tex>c = \log_b a = c </tex> <tex>\Rightarrow</tex> <tex dpi = "130"> T(n) = \displaystyle\sum_{i=10}^{\log_b n}n^c\cdot\left(\frac{a}{b^c}\right)^i = </tex> <tex dpi = "130> n^c\cdot\displaystyle\sum_{i=10}^{\log_b n}\left(\frac{a}{b^c}\right)^i = n^c\cdot\displaystyle\sum_{i=10}^{\log_b n}1^i = n^c + n^c\log_b n = \ThetaO\left( n^{c} \log n \right) </tex>#<tex>c < \log_b a > c </tex> <tex>\Rightarrow</tex> <tex dpi = "125"> T(n) = \displaystyle\sum_{i=10}^{\log_b n}n^c\cdot\left(\frac{a}{b^c}\right)^i = n^c\cdot\displaystyle\sum_{i=10}^{\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 = "150130"> = </tex> <tex dpi = "150130"> n^{\log_b a} \ThetaRightarrow T(n) = O\left( n^{\log_b a} \right) </tex>

Пусть при решении поставленной задачиМастер-теорема имеет прямое отношение к анализу алгоритмов, существует алгоритм, который разбивает ее на так как рекуррентное соотношение можно воспринимать следующим образом: имеется задача размера <tex> a n </tex> подзадач,при этом алгоритм разбивает её на <tex>na </tex> — размер общей задачи, подзадач размера <tex dpi = "125">\dfrac{n}{b}</tex> — размер каждой подзадачи, тратит дополнительно <tex> O(n ^ {c} ) </tex> — стоимость работы действий, а если размер подзадачи становится равен единице, проделанной рекурсивными вызовамито алгоритму требуется <tex>O(1)</tex> действий на её решение.  Из доказательства теоремы видно, который включает что если в себя стоимость деления проблемы рекурретном соотношении заменить <tex> O </tex> на <tex> \Theta </tex> и <tex> \Omega </tex>, то и стоимость слияния асимптотика решения подзадач и изменится соответствующим образом на <tex>d\Theta </tex> — начальная стоимость для данной задачи(при или <tex>n = 1\Omega </tex>).Тогда мастер-теорема позволяет найти асимптотическое решение рекурренты, возникшей в результате анализа асимптотики данной задачи.

<tex> t(xn) = \begin{cases} 3 2 \; t\!\left(\dfrac{xn}{2}\right) + x^{2} O(n\log n) , & x \ge 2n > 1\\ 5x 1 , & n = 1 \le x < 2

Заметим, чтобы узнать что <tex>tn\log n = O(7n^c)</tex> , мы должны знать для любого <tex>t\left(\dfrac{7}{2}\right)c > 1 </tex>, чтобы узнать что удовлетворяет 1 условию. Тогда <tex>t\leftT(\dfrac{7}{2}\rightn)</tex>, мы должны узнать <tex>t\left= O(\dfrac{7}{4}\rightn^c)</tex>, где <tex> c >1 < \dfrac{7}{4} < 2</tex>, тогда при <tex>t\left(\dfrac{7}{4}\right) a = \dfrac{35}{4}</tex> , <tex>t\left(\dfrac{7}{2}\right) = 3\cdot\dfrac{35}{4} + \dfrac{49}{4}</tex>, тогда <tex>t(7) b = 3t\left(\dfrac{7}{2}, \right) + 7^2 log_b a = \dfrac{329}{2}1</tex>

2 \; T\!\left(\dfrac{n}{3}\right) + O(f(n)) , & n > 1\\

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

Рассмотрим пару ошибочносоотношений, которые нельзя решить мастер-составленных соотношенийтеоремой:*<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\fracleft(\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> , однако пример можно решить следующим образом: заметим, что на < 1 не может быть меньше одной подзадачи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) = 64T-2T\left (\dfrac{n}{83}\right )-+O(n^2\log n)</tex>*:<tex>f(n)a < 0 </tex>, при составлении асимптотического решения перед <tex> O </tex> не положительнакаждый раз будет новый знак, что противоречит мастер-теореме. 

| <tex>T(n) = T\left(\fracdfrac{n}{2}\right) + O(1)</tex>

| <tex>T(n) = 2 T\left(\fracdfrac{n}{2}\right) + O(1)</tex>

| <tex>T(n) = 2 T\left(\fracdfrac{n}{2}\right) + O(n)</tex>