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

Заметим, что если от схемы требуется хранить множества размером не более n, то она должна использовать не менее <math>\lceil log \; \sum_{i \le n} \tbinom{m}{i} \rceil</math> бит. Если <math>n \le m^{1 - \Omega(1)}</math>, это означает, что схема должна хранить <math>\Omega(n \; log \; m)</math> бит (и, следовательно, использовать <math>\Omega(n)</math> ячеек). Целью работы [2] является получение схемы, которая отвечает на запросы с помощью постоянного числа битовых зондов и при этом использует таблицу размером <math>\O(n \; log \; m)</math> бит.