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

На интуитивном уровне их аргументация выглядит следующим образом. В жестком экземпляре будет <math>n</math> случайных обновлений, за которыми следует один случайный запрос. Оставим <math>r \ge 2</math> для последующего определения. Идя ''назад'' по времени от запроса, можно сгруппировать обновления в экспоненциально растущие ''эпохи'': последние <math>r</math> обновлений – это эпоха 1, более ранние <math>r^2</math> обновлений – эпоха 2 и т. д. Обратите внимание, что номера эпох увеличиваются с течением времени, и всего существует <math>O(log_r \; n)</math> эпох.

Для некоторой эпохи <math>i</math> рассмотрим раскрытие в запросе всех обновлений, выполненных во все эпохи, отличные от <math>i</math>. Тогда запрос сводится к запросу частных сумм среди обновлений в эпоху <math>i</math>. Если запрос не касается индекса ниже минимального индекса, обновленного в эпоху <math>i</math>, ответ на запрос остается равномерно случайным, то есть имеет <math>\delta</math> бит энтропии. Более того, даже если дано, скажем, <math>r_i \delta/100</math> бит информации об эпохе <math>i</math>, ответ все равно имеет в среднем <math>\Omega(\delta)</math> бит энтропии. Это происходит потому, что запрос и обновления в эпоху <math>i</math> равномерно случайны, поэтому запрос может касаться любой частной суммы этих обновлений равномерно случайным образом. Каждая из частных сумм <math>r_i</math> является независимой случайной переменной от энтропии <math>\delta</math>.

2. В эпохи <math>1, ..., i - 1</math> было записано <math>b t_u^{\Sigma} \cdot \sum_{j = 1}^{i - 1} r^j \le b t_u^{\Sigma} \cdot 2 r^{i - 1}</math> бит. Это меньше, чем <math>r_i \delta/100</math> бит информации для <math>r > 200 t_u^{\Sigma}</math> (вспомним предположение <math>\delta = b</math>). Из вышесказанного следует, что ответ на запрос все еще имеет <math>\Omega(\delta)</math> бит энтропии.

3. Поскольку значение <math>i</math> равномерно случайно среди <math>\Theta(log_r \; n)</math> эпох, запрос делает ожидаемое число <math>\Theta(t_q^{\Sigma}/log_r \; n)</math> зондирований ячеек из эпохи <math>i</math>. Все запросы, которые не делают ни одного зондирования ячеек в эпоху <math>i</math>, получают фиксированный ответ (энтропия 0), а все остальные запросы получают ответы с энтропией менее <math>\delta</math>. Поскольку средний запрос имеет энтропию <math>\Omega(\delta)</math>, запрос должен зондировать ячейку из эпохи <math>i</math> с константной вероятностью. Это означает, что <math>t_q^{\Sigma} / log_r \; n = \Omega(1)</math>, а <math>\sum = \Omega(log_r \; n) = \Omega(lg \; n/lg \; t_u^{\Sigma})</math>.

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