4817
правок
Нижняя граница для динамической связности: различия между версиями
Перейти к навигации
Перейти к поиску
Нижняя граница для динамической связности (посмотреть исходный код)
Версия от 08:41, 18 августа 2025
, 18 август→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача о динамической связности требует поддержки структуры графа G следующими операциями: | Задача о динамической связности требует поддержки структуры графа <math>G</math> следующими операциями: | ||
'''insert'''(u, v): вставка неориентированного ребра (u, v) в граф; | '''insert'''(u, v): вставка неориентированного ребра (u, v) в граф; | ||
| Строка 12: | Строка 12: | ||
Пусть <math>m</math> – верхняя граница количества ребер в графе. В данной статье обсуждаются нижние границы клеточного зонда для этой задачи. Обозначим за <math>t_u</math> сложность вставки и удаления, а за <math>t_q</math> – сложность | Пусть <math>m</math> – верхняя граница количества ребер в графе. В данной статье обсуждаются нижние границы клеточного зонда для этой задачи. Обозначим за <math>t_u</math> сложность вставки и удаления, а за <math>t_q</math> – сложность проверки. | ||
| Строка 26: | Строка 26: | ||
Чтобы полностью сформулировать задачу, будем считать, что элементы A[i] берутся из произвольной группы G, содержащей не менее | Чтобы полностью сформулировать задачу, будем считать, что элементы <math>A[i]</math> берутся из произвольной группы <math>G</math>, содержащей не менее <math>2^{\delta}</math> элементов. В модели клеточного зонда с b-битными ячейками обозначим за <math>t_u^{\Sigma}</math> сложность обновления (update), а за <math>t_q^{\Sigma}</math> – сложность проверки (testsum) (которая также является нижней границей sum). | ||
Компромисс между | Компромисс между <math>t_u^{\Sigma}</math> и <math>t_q^{\Sigma}</math> хорошо изучен для всех значений <math>b</math> и <math>\delta</math>. Далее будут рассматриваться только нижние границы при стандартных предположениях, что <math>b = \Omega(lg \; n)</math> и <math>t_u \ge t_q</math>. Стандартным является предположение <math>b = \Omega(lg \; n)</math> для верхних границ в модели с оперативной памятью; это предположение также означает, что нижняя граница применима к машине с указателями. При этих условиях Петрашку и Демейн [6] доказали следующее утверждение: | ||
Теорема 1. Сложность задачи о частных суммах удовлетворяет соотношению: | '''Теорема 1. Сложность задачи о частных суммах удовлетворяет соотношению: <math>t_q^{\Sigma} \cdot lg(t_u^{\Sigma} / t_q^{\Sigma}) = \Omega(\delta/b \cdot lg \; n)</math>.''' | ||
| Строка 56: | Строка 56: | ||
Нижняя граница Теоремы 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]. | Нижняя граница Теоремы 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]. | ||
== Основные результаты == | |||
'''Понимание иерархий''' | '''Понимание иерархий''' | ||