59
правок
Изменения
Нет описания правки
*:рассмотрим <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> O(n) = c \cdot n i </tex>шаге, тогда размер <tex> T(ni) = O(\le \dfrac{n) }{4^i} </tex>. Докажем по индукции, что тогда оценивая сумму состоящую из <tex> T(\dfrac{n) \le cn \cdot k }{4^i} </tex> , где и <tex> k - maxO(2, dn), d - </tex> стоимость задачи, при видим, что <tex> T(n ) = 1 </tex>. База: <tex> O(n = 1 </tex> - верно (<tex> T(1) \le k </tex>). Переход: *<texdpi = "130"> T(n) = 0.5T-2T\left(\dfrac{n}{23}\right) + cn \le \dfrac{ckn}{4} + cn \le \dfrac{ckn}{4} + 3 \cdot \dfrac{ckn}{4} \le ckn O(n^2)</tex> Откуда видно*:<tex> a < 0 </tex>, что при составлении асимптотического решения перед <tex> T(n) = O(n) </tex>каждый раз будет новый знак, что противоречит мастер-теореме.
=== Приложение к известным алгоритмам ===
{| class="wikitable"
