4817
правок
Нижняя граница для динамической связности: различия между версиями
Перейти к навигации
Перейти к поиску
м
Нижняя граница для динамической связности (посмотреть исходный код)
Версия от 09:20, 18 августа 2025
, 18 август→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 62: | Строка 62: | ||
'''Эпохи''' | '''Эпохи''' | ||
Для описания техник, связанных с нижними границами, сначала рассмотрим запрос | Для описания техник, связанных с нижними границами, сначала рассмотрим запрос '''sum''' и предположим, что <math>\delta = b</math>. В 1989 году Фредман и Сакс [3] положили начало изучению нижних границ динамических клеточных зондов, по сути, доказав нижнюю границу <math>t_q^{\Sigma} \; lg \; t_u^{\Sigma} = \Omega(lg \; n)</math>. Заметим, что это означает, что <math> max \{ t_q^{\Sigma}, t_u^{\Sigma} \} = \Omega(lg \; n/lg \; lg \; n)</math>. | ||
На интуитивном уровне их аргументация выглядит следующим образом. В жестком экземпляре будет n случайных обновлений, за которыми следует один случайный запрос. Оставим r > | На интуитивном уровне их аргументация выглядит следующим образом. В жестком экземпляре будет <math>n</math> случайных обновлений, за которыми следует один случайный запрос. Оставим <math>r \ge 2</math> для последующего определения. Идя ''назад'' по времени от запроса, можно сгруппировать обновления в экспоненциально растущие ''эпохи'': последние <math>r</math> обновлений – это эпоха 1, более ранние <math>r^2</math> обновлений – эпоха 2 и т. д. Обратите внимание, что номера эпох увеличиваются с течением времени, и всего существует <math>O(log_r \; n)</math> эпох. | ||
Для некоторой эпохи i рассмотрим раскрытие в запросе всех обновлений, выполненных во все эпохи, отличные от i. Тогда запрос сводится к запросу частных сумм среди обновлений в эпоху i. Если запрос не касается индекса ниже минимального индекса, обновленного в эпоху i, ответ на запрос остается равномерно случайным, то есть имеет | Для некоторой эпохи <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>. | ||
Теперь можно поинтересоваться, сколько информации доступно для запроса. Пусть в момент запроса каждая ячейка связана с эпохой, в которую она была записана в последний раз. Выбрав эпоху i равномерно случайным образом, можно привести следующие интуитивные соображения: | Теперь можно поинтересоваться, сколько информации доступно для запроса. Пусть в момент запроса каждая ячейка связана с эпохой, в которую она была записана в последний раз. Выбрав эпоху <math>i</math> равномерно случайным образом, можно привести следующие интуитивные соображения: | ||