Изменения

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

Алгоритм Балабана

12 байт добавлено, 13:54, 15 ноября 2013
Основы алгоритма
Для начала рассчитаем место, необходимое для выполнения алгоритма. Алгоритм использует рекурсивную функцию <tex>TreeSearch</tex>. Последовательность вызовов функции может занять память. Эта последовательность может быть представлена как путь корня рекурсивного дерева, до узла. Назовем этот узел, и соответствующий вызов ''активным''. Активный вызов занимает <tex>O(N)</tex> памяти, каждый его "предок" занимает <tex>O(|I_v| + |Q_v|)</tex> памяти, а остальные структуры используют <tex>O(N)</tex>. Очевидно, что любой путь <tex>pt</tex> от корня рекурсивного дерева до какого-то узла <tex>\sum_{v \in pt}(|I_v + |Q_v|) = O(N)(|I_v| \le b_v - a_v \le \lceil (b_{ft(v)} - a_{ft(v)})/2 \rceil)</tex>.
 В итоге, место, требуемое для работы алгоритма - требуется <tex>O(N)</tex>памяти.
==Время работы==
Анонимный участник

Навигация