Нижняя граница для динамической связности: различия между версиями

Нижняя граница вытекает из реализации операций поддержки частных сумм с помощью операций поддержки динамической связности. На рис. 1 вершины графа образуют целочисленную сетку размером n x n. Каждая вершина инцидентна не более чем двум ребрам, одно из которых соединяется с вершиной в предыдущем столбце, а другое – с вершиной в следующем столбце. Точка (x;y1) в сетке соединена с точкой (x + 1;A[x](y1)), т. е. ребра между двумя смежными столбцами описывают соответствующую перестановку из вектора частных сумм.

Чтобы реализовать операцию update(x, ж), сначала удаляются все ребра между столбцами x и x + 1, а затем вставляются новые ребра в соответствии с ж. Это дает tJ = O(2n - tu) Для реализации testsum(x, ж) можно использовать n связанных запросов между парами точек (1; у) ^" (х + 1,л{у)). Тогда tq = O(n ■ tq). Заметим, что запрос суммы не может быть реализован так же просто. Динамическая связность является основным мотивом для изучения запроса testsum.

Нижняя граница Теоремы 1 соответствует ntq ■ lg(2ntu/ntq) = Q{n\gn); следовательно, tqlg(tu/tq) = £2(lgn). Заметим, что из этой нижней границы следует maxf tu; tq g = Q (lg n). Лучшая известная верхняя граница (с использованием амортизации и рандомизации) равна O(lg n(lglg n)3) [ ]. Известно, что для любого tu = £?(lg n(lglg n)3) компромиссная нижняя граница является строгой. Отметим, что граф в нижней границе всегда является несвязным объединением путей. Из этого следует оптимальность нижних границ для двух важных частных случаев: динамических деревьев [8] и динамической связности в планарных графах [2].