Изменения

|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 dpi = "130"> T(n) = \displaystyle\sum_{i=0}^{\log_b n}O\left(n^c\cdot\left(\frac{a}{b^c} \right)^i\right) + O(1)\right)^i= О\left(n^c\cdot\displaystyle\sum_{i=0}^{\log_b n}\left(\frac{a}{b^c} \right)^i + O(1)\right)\right)^i</tex>

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

*:<tex>a < 1</tex> не может быть меньше одной подзадачи. Однако пример можно решить следующим образом: пусть <tex> O(n) = c \cdot n </tex>, тогда <tex> T(n) = O(n) </tex>. Докажем по индукции, что <tex> T(n) \le cn \cdot k </tex> , где <tex> k - max(2, d), d - </tex> стоимость задачи, при <tex> n = 1 </tex>. База: <tex> n = 1 </tex> - верно (<tex> T(1) \le k </tex>). Переход: <tex> T(n) = 0.5T \cdot \dfrac{n}{2} + cn \le \dfrac{ckn}{4} + cn \le \dfrac{ckn}{4} + 3 \cdot \dfrac{ckn}{4} \le ckn </tex>  Откуда видно, что <tex> T(n) = O(n) </tex>.