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

Следует оценить двойственность между техникой доказательства и естественными верхними границами, основанными на иерархии. Рассмотрим верхнюю границу, основанную на дереве степени r. Последние r случайных обновлений (эпоха 1), вероятно, равномерно распределены в массиве. Это означает, что обновления касаются разных дочерних элементов корня. Аналогично, r2 обновлений в эпоху 2, скорее всего, коснутся каждого узла на втором уровне дерева, и так далее. Нижняя граница свидетельствует, что запрос должен пройти путь от корня к листьям, прощупывая узел на каждом уровне дерева (что эквивалентно одной ячейке из каждой эпохи).

Несмотря на значительное усовершенствование техники нижних границ, нижняя граница £2(\gn/\g\gn) не была улучшена до 2004 года. Тогда Петрашку и Демейн [ ] показали оптимальное ограничение tq \g(t*/tf) = £2(\g n), что означает max{fjf, tf} = £2(lg n). Для простоты нижеследующее обсуждение пренебрегает этим компромиссом и просто набрасывает нижнюю границу Q (lg n).

Техника подсчета Петрашку и Демейна [ ] довольно сильно отличается от техники эпох; см. рис. 2. Жесткий экземпляр представляет собой последовательность из n операций, чередующих обновления и запросы. Они рассматривают сбалансированное бинарное дерево на временной оси, каждый лист которого является операцией. Теперь для каждого узла дерева авторы предлагают подсчитать количество клеточных зондирований, выполненных в правом поддереве, относительно клетки, записанной в левом поддереве. Каждое зондирование подсчитывается ровно один раз, для получения наименьшего общего предка времен чтения и записи.

Рисунок 2. Анализ зондирования клеток в методах a, основанном на эпохах, и b, основанном на иерархии времени

Теперь рассмотрим два «братских» поддерева, каждое из которых содержит k операций. Предполагается, что k/2 обновлений в левом поддереве и k/2 запросов в правом поддереве будут чередоваться в пространстве индексов. Таким образом, запросы в правом поддереве запрашивают Q(k) различных частных сумм обновлений в левом поддереве. Таким образом, правому поддереву «нужно» Q(k&) бит информации о левом поддереве, и эта информация может поступать только из ячеек, записанных в левом поддереве и прочитанных в правом. Отсюда следует нижняя граница в Q(k) зондов, связанных с родителем «братских» поддеревьев. Эта граница линейна по числу листьев, так что, суммируя по всему дереву, мы получаем полную нижнюю границу Q(n\g n), или стоимость £?(lg n) на операцию.