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(\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>
