Изменения

Перейти к: навигация, поиск

Мастер-теорема

1 байт убрано, 19:37, 4 сентября 2022
м
rollbackEdits.php mass rollback
<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 ====
1632
правки

Навигация