4817
правок
Полностью динамическая связность: верхняя и нижняя границы: различия между версиями
Материал из WEGA
Полностью динамическая связность: верхняя и нижняя границы (посмотреть исходный код)
Версия от 15:24, 12 июля 2014
, 12 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 43: | Строка 43: | ||
Во время поиска на уровне | Во время поиска на уровне <math>\ell \;</math> подходящим образом выбранные древесные и недревесные дуги могут быть перемещены на более высокий уровень следующим образом. Пусть <math>T_v</math> и <math>T_w</math> – деревья в лесу <math>F_{\ell }</math>, полученные после удаления дуги (v, w), и пусть, без ограничения общности, <math>T_v</math> меньше <math>T_w</math>. Тогда <math>T_v</math> содержит не более <math>n/2^{\ell + 1}</math> вершин, поскольку <math>T_v \cup T_w \cup \{ (v, w) \} </math> было деревом на уровне <math>\ell \;</math> и выполняется инвариант (2). Следовательно, дуги уровня <math>\ell \;</math> в <math>T_v</math> могут быть перемещены на уровень <math>\ell + 1\;</math> с сохранением инвариантов. Наконец, одна за дугой посещаются недревесные дуги, инцидентные <math>T_v</math>: если дуга соединяет <math>T_v</math> и <math>T_w</math>, то дуга замены найдена и поиск останавливается; в противном случае ее уровень увеличивается на 1. | ||
Деревья каждого леса поддерживаются таким образом, что базовые операции, необходимые для реализации вставки и удаления дуг, могут быть выполнены за время O(log n). Имеются несколько вариантов базовых структур данных, которые могут выполнить такую задачу; например, для этой цели можно использовать деревья Эйлерова пути (ET-деревья), впервые предложенные в [ ]. | Деревья каждого леса поддерживаются таким образом, что базовые операции, необходимые для реализации вставки и удаления дуг, могут быть выполнены за время O(log n). Имеются несколько вариантов базовых структур данных, которые могут выполнить такую задачу; например, для этой цели можно использовать деревья Эйлерова пути (ET-деревья), впервые предложенные в [ ]. | ||
Помимо вставки и удаления дуг из леса, ET-деревья также могут поддерживать такие операции, как нахождение в лесу дерева, содержащего заданную вершину, вычисление размера дерева и, что еще более важно, нахождение древесных дуг уровня | |||
Помимо вставки и удаления дуг из леса, ET-деревья также могут поддерживать такие операции, как нахождение в лесу дерева, содержащего заданную вершину, вычисление размера дерева и, что еще более важно, нахождение древесных дуг уровня <math>\ell \;</math> в дереве Tv и недревесных дуг уровня <math>\ell \;</math>, инцидентных Tv. Это можно сделать за счет дополнения ET-деревьев константным количеством информации для каждой вершины; подробнее об этом – в [11]. | |||
Используя идею амортизации на базе изменений уровня, можно доказать заявленную границу времени обновления в размере O(log2 n). В частности, вставка дуги и повышение ее уровня требуют времени O(log n). Поскольку это может случиться O(log n) раз, полная амортизированная стоимость вставки, включающая повышение уровня, составляет O(log 2n). Что касается удалений дуг, полная стоимость операций обрезания и связывания леса O(log n) составляет O(log 2n); кроме того, имеется O(log n) рекурсивных вызовов процедуры Replace, каждый из них стоимостью O(log n), плюс амортизированная стоимость операций повышений уровня. ET-деревья над F0 = F позволяют получать ответы на запросы о связности за время O(log n) в наихудшем случае. Как было показано в [11], это время может быть уменьшено до O(log n/loglog n) в случае использования @(log n)-арной версии ET-деревьев. | Используя идею амортизации на базе изменений уровня, можно доказать заявленную границу времени обновления в размере O(log2 n). В частности, вставка дуги и повышение ее уровня требуют времени O(log n). Поскольку это может случиться O(log n) раз, полная амортизированная стоимость вставки, включающая повышение уровня, составляет O(log 2n). Что касается удалений дуг, полная стоимость операций обрезания и связывания леса O(log n) составляет O(log 2n); кроме того, имеется O(log n) рекурсивных вызовов процедуры Replace, каждый из них стоимостью O(log n), плюс амортизированная стоимость операций повышений уровня. ET-деревья над F0 = F позволяют получать ответы на запросы о связности за время O(log n) в наихудшем случае. Как было показано в [11], это время может быть уменьшено до O(log n/loglog n) в случае использования @(log n)-арной версии ET-деревьев. | ||
