4511
правок
Приближенные словари: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 91: | Строка 91: | ||
Из Теоремы 6 также следует, что любая детерминированная схема, отвечающая на запросы с использованием t битовых зондов, в наихудшем случае должна занимать не менее ntm ^ | Из Теоремы 6 также следует, что любая детерминированная схема, отвечающая на запросы с использованием t битовых зондов, в наихудшем случае должна занимать не менее <math>ntm^{\Omega(1/t)}</math> бит памяти. Последний результат доказывает существование схем, почти соответствующих нижней границе. | ||
Теорема 7. | '''Теорема 7.''' | ||
1. Существует неадаптивная схема, которая хранит множества размером не более n из совокупности размера m с использованием O( | '''1. Существует неадаптивная схема, которая хранит множества размером не более n из совокупности размера m с использованием <math>O(ntm^{\frac{2}{t + 1}})</math> бит памяти и отвечает на запросы с использованием 2t + 1 битовых зондов. Это неявная схема.''' | ||
2. Существует явная адаптивная схема, которая хранит множества размером не более n из совокупности размера m с использованием O( | '''2. Существует явная адаптивная схема, которая хранит множества размером не более n из совокупности размера m с использованием <math>O(m^{1/t} n \; log \; m)</math> бит памяти и отвечает на запросы с использованием O(log n + loglog m) + t битовых зондов.''' | ||
== Применение == | == Применение == | ||
