1632
правки
Изменения
м
Умные люди могут сразу же заметить, что решением Решением этого является <tex>T(n) = O(n \log n)</tex>. А люди моего уровня могут почитать умные книжки или просто поверить в данный факт. Хотя могу неформально пояснить: второе слагаемое даёт <tex>O(n)</tex> суммарно, а всего слагаемых из-за неё получится <tex>O(\log n)</tex>. То есть получим <tex>O(n)</tex> из-за второго слагаемого и ещё <tex>O(\log n)</tex> слагаемых вида <tex>O(n)</tex>.
Нетрудно заметитьГлубина дерева рекурсии равна <tex>\log_4 n = \frac{1}{2}\log_2 n</tex>Следовательно, что <tex>Q(n) = O(2^{\frac{1}{2}\log_2 n}) = O(\sqrt n)</tex> является решением. Принимая во внимание всё, что писалось выше, получаем требуемое.
rollbackEdits.php mass rollback
<tex>T(n) = O(n) + 2 \cdot T(n / 2)</tex>, otherwise.
Также стоит отметить, что можно и не искать медиану за линейное время, а просто посортить все точки в самом начале и дальше использовать это. В реализации попроще, асимптотика та же.
<tex>Q(n) = 2 + 2 \cdot Q(n / 4)</tex>, otherwise.
}}
By the way, в общем случае время на запрос <tex>O(n^{1 - 1/k} + ans)</tex>. Быстренько прикинув, я получил соотношение из соотношения <tex>Q(n) = k + 2^{k - 1} \cdot Q(n / 2^k)</tex>. Кажется, так и есть, но это не особо надо, просто пусть будет, полезно же.
== Ссылки ==
