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

Несмотря на значительное усовершенствование техники нижних границ, нижняя граница <math>\Omega(lg \; n/lg \; lg \; n)</math> не была улучшена до 2004 года. Тогда Петрашку и Демейн [6] представили оптимальную границу <math>t_q^{\Sigma} lg(t_u^{\Sigma}/t_q^{\Sigma}) = \Omega(lg \; n)</math>, из чего следует <math>max \{ t_u^{\Sigma}, t_q^{\Sigma} \} = \Omega(lg \; n)</math>. Для простоты нижеследующее обсуждение пренебрегает этим компромиссом и просто набрасывает нижнюю границу <math>\Omega(lg \; n)</math>.

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