Приближенные словари: различия между версиями

'''Теорема 2. Предположим, что <math>\frac{n}{m^{1/3}} \le \epsilon \le \frac{1}{4}</math>. Тогда любой рандомизированной схеме с двухсторонней <math>\epsilon</math>-ошибкой, отвечающей на запросы с помощью одного битового зонда, требуется объем памяти <math>\Omega \big( \frac{n}{\epsilon \; log(1/\epsilon)} \; log \; m \big)</math>.'''

'''Теорема 4. Предположим, что <math>\frac{n}{m^{1/3}} \le \epsilon \le \frac{1}{4}</math>. Рассмотрим статическую задачу о принадлежности для множества S размера не более n из совокупности размера m. Тогда любая схема с односторонней <math>\epsilon</math>-ошибкой, отвечающая на запросы с использованием не более одного битового зонда, должна использовать  <math>\Omega \big( \frac{n^2}{\epsilon^2 \; log(n/\epsilon)} \; log \; m \big)</math> бит памяти.'''

Теорема 5. Предположим, что 0 < S < 1. Существует рандомизированная схема с односторонней ошибкой n, которая решает статическую задачу о принадлежности, используя O(n1+S log m) бит памяти и O(j) битовых зондов.

Теорема 6. Предположим, что детерминированная схема хранит подмножества размера n из совокупности размера m, используя биты памяти, и отвечает на запросы о принадлежности с помощью t битовых зондов с запросами к памяти. Тогда (™) < max,<nt (2/).

У этого компромиссного результата есть интересное следствие. Вспомним, что схема хэширования FKS представляет собой структуру данных для хранения множеств размером не более n из совокупности размера m с использованием O(n log m) бит, так что на запросы о принадлежности можно отвечать с использованием O(log m) битовых зондов. В качестве следствия компромиссного результата в работе [ ] показано, что схема FKS применяет оптимальное количество битовых зондов с постоянным коэффициентом для данного объема памяти.

Следствие 1. Пусть e > 0; c > 1 – любые константы. Существует константа 8 > 0, такая, что верно следующее утверждение. Пусть n < ml~€, и пусть задана схема хранения множеств размером не более n из совокупности размера m в виде структур данных размером не более cn log m бит. Тогда любой детерминированный алгоритм, отвечающий на запросы о принадлежности, используя эту структуру, должен в наихудшем случае использовать не менее S log m битовых зондов.