1632
правки
Изменения
м
rollbackEdits.php mass rollback
Заметим, что количество операций увеличивается, уменьшается и остается константой, если <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> 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>
