Изменения

# Если <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> 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> : <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 dpi = "130"> \cdot \displaystyle\sum_{i=10}^{\log_b n}n^c\left(\frac{a}{b^c}\right)^i = O\left(n^c\cdot\displaystyle\sum_{i=10}^{\log_b n}\left(\frac{a}{b^c}\right)^i\right)</tex> 

#<tex>\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>\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>\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 </tex> подзадач,при этом <tex>n</tex> — размер общей задачи, <tex dpi = "125">\dfrac{n}{b}</tex> — размер каждой подзадачи, <tex> n ^ {c} </tex> — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач и <tex>dO(1)</tex> — начальная стоимость для данной задачи(при <tex>n = 1</tex>).Тогда мастер-теорема позволяет найти асимптотическое решение рекурренты, возникшей в результате анализа асимптотики данной задачи.

3 2 \; t\!\left(\dfrac{x}{2}\right) + n\sqrt{log n + 1} , & n > 1\\

Рассмотрим Заметим, что <tex> f(n) = n\sqrt{log n+1} = \ThetaO(n^{3/2}c) </tex> , тогда данное соотношение удовлетворяет случаю для любого <tex> c < \log_b a> 1 </tex>, а именно что удовлетворяет 1 условию. Тогда <tex> \dfrac{3}{2} < \log_2 3 T(n) = O(n^c) </tex>, тогдаасимптотикой является где <tex> \Theta(n ^ {\log_2 3}) c > 1 </tex>.

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

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

*:рассмотрим <tex> f(n) = \dfrac{n}{\log n} </tex> , тогда не существует такого полинома<tex> f(n) = O(n^c), c \ge 1 </tex> , что тогда <tex> \dfrac{f(n)}{\log n^1} \in \Theta(n^c) </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>