4511
правок
Приближенные словари: различия между версиями
Перейти к навигации
Перейти к поиску
м
нет описания правки
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Статическая задача о принадлежности; приближенная задача о принадлежности == Постановка задачи == '''Задача и модель''' Задача о статической структуре данных состоит из набора данных D, набора запросов Q, набора ответов A и фу...») |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 78: | Строка 78: | ||
'''Детерминированные схемы''' | '''Детерминированные схемы''' | ||
Бурман и коллеги показали, что детерминированные схемы, в отличие от рандомизированных, демонстрируют | Бурман и коллеги показали, что детерминированные схемы, в отличие от рандомизированных, демонстрируют компромиссное соотношение времени и памяти. | ||
| Строка 84: | Строка 84: | ||
У этого компромиссного результата есть интересное следствие. Вспомним, что схема хэширования FKS представляет собой структуру данных для хранения множеств | У этого компромиссного результата есть интересное следствие. Вспомним, что схема хэширования FKS представляет собой структуру данных для хранения множеств размером не более n из совокупности размера m с использованием O(n log m) бит, так что на запросы о принадлежности можно отвечать с использованием O(log m) битовых зондов. В качестве следствия компромиссного результата в работе [ ] показано, что схема FKS применяет оптимальное количество битовых зондов с постоянным коэффициентом для данного объема памяти. | ||