3622
правки
Изменения
м
→Недопустимые соотношения
Рассмотрим пару соотношений, которые нельзя решить мастер-теоремой:
*<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(\frac{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> T(i) \leqslant \dfrac{c \cdot n}{4^i} </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> каждый раз будет новый знак, что противоречит мастер-теореме.
