1632
правки
Изменения
м
Откуда видно, что <tex> T(n) = O(n) </tex>.
rollbackEdits.php mass rollback
|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>\left(\dfrac{a}{b^c}\right)^i</tex> больше <tex>1</tex>, равна <math>1</math> или меньше <math>1</math>. Рассмотрим <tex dpi = "130">\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</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)= ОO\left(n^c\cdot\displaystyle\sum_{i=0}^{\log_b n}\left(\frac{a}{b^c}\right)^i + O(1)\right)</tex>
Откуда получаем:
}}
Мастер-теорема имеет прямое отношение к анализу алгоритмов, так как рекуррентное соотношение можно воспринимать следующим образом: имеется задача размера <tex> n </tex> , алгоритм разбивает её на <tex> a </tex> подзадач размера <tex> \dfrac{n}{b} </tex> , тратит дополнительно <tex> O(n^c) </tex> действий, а если размер подзадачи становится равен единицыединице, то алгоритму требуется <tex>O(1)</tex> действий на её решение. Мастер-теорема работает также при замене Из доказательства теоремы видно, что если в рекурретном соотношении заменить <tex> O </tex> на <tex> \Theta </tex> и <tex> \Omega </tex> , то и асимптотика решения изменится соответствующим образом (на <tex> O \rightarrow \Theta, O \rightarrow </tex> или <tex> \Omega </tex>).
==Примеры==
<tex> t(xn) = \begin{cases} 2 \; t\!\left(\dfrac{xn}{2}\right) + O(n\log n) , & n > 1\\
1 , & n = 1
\end{cases}
</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>
==== Пример 2 ====
Рассмотрим пару соотношений, которые нельзя решить мастер-теоремой:
*<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\left(\fracdfrac{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> не может быть меньше одной подзадачи. Однако , однако пример можно решить следующим образом: пусть заметим, что на <tex> i </tex> шаге, размер <tex> OT(ni) = \leqslant \dfrac{c \cdot n }{4^i} </tex>, тогда , оценивая сумму, получаем, что <tex> T(n) = O(n) </tex>. Докажем по индукции, что *<texdpi = "130"> T(n) = -2T\le cn left (\dfrac{n}{3}\cdot k </tex> , где <tex> k - maxright )+O(n^2, d), d - </tex> стоимость задачи, при <tex> n = 1 </tex>. База*: <tex> n = 1 a < 0 </tex> - верно (, при составлении асимптотического решения перед <tex> T(1) \le k O </tex>)каждый раз будет новый знак, что противоречит мастер-теореме. Переход: <tex> T(n) = 0.5T\left(\dfrac{n}{2}\right) + cn \le \dfrac{ckn}{4} + cn \le \dfrac{ckn}{4} + 3 \cdot \dfrac{ckn}{4} \le ckn </tex>
=== Приложение к известным алгоритмам ===
{| class="wikitable"
