3622
правки
Изменения
→Недопустимые соотношения
*:рассмотрим <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> T(i) \leqslant \dfrac{n}{4^i} </tex> , тогда , оценивая сумму состоящую из <tex> \dfrac{n}{4^i} </tex> и <tex> O(n) </tex>, видимполучаем, что <tex> T(n) = O(n) </tex>.
*<tex dpi = "130">T(n) = -2T\left (\dfrac{n}{3}\right )+O(n^2)</tex>
*:<tex> a < 0 </tex>, при составлении асимптотического решения перед <tex> O </tex> каждый раз будет новый знак, что противоречит мастер-теореме.
=== Приложение к известным алгоритмам ===
{| class="wikitable"
