Изменения

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

Алгоритм Тарьяна поиска LCA за О(1) в оффлайне

355 байт добавлено, 16:45, 6 июня 2014
м
Оценка сложности
Во-вторых, операции по объединению множеств, которые в сумме для всех разумных <tex>n</tex> затрачивают <tex>O (n)</tex> операций.
 
Каждый запрос <tex>(u, v)</tex> будет рассмотрен дважды {{---}} при посещение вершины <tex>u</tex> и <tex>v</tex>, но обработан лишь один раз, поэтому можно считать, что все запросы обработаются суммарно за <tex>O (m)</tex>.
В-третьих, для каждого запроса проверка условия и определение результата, опять же, для всех разумных <tex>n</tex> выполняется за <tex>O (1)</tex>. Итоговая асимптотика получается <tex>O (n + m)</tex>, но при достаточно больших <tex>m</tex> ответ за <tex>O (1)</tex> на один запрос.
74
правки

Навигация