Изменения

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

Ортогональный поиск

1 байт добавлено, 02:37, 16 июня 2012
Одномерный случай
Алгоритм работает за <tex>O(\log n + T)</tex>, где <tex>T</tex> - количество точек в ответе.<br>
 
'''Примечание:''' если задача сформулирована так, что нужно вывести все искомые точки, то запрос не может выполняться быстрее, чем за <tex>O(T)</tex>. Однако, далеко не во всех задачах ортогонального поиска нужно получать все точки в явном виде. Поэтому далее время, необходимое для вывода ответа, будет опускаться в оценке времени запроса.
Анонимный участник

Навигация