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

Приближенные словари (посмотреть исходный код)

133 байта добавлено , 4 ноябрь

4511

правок

Версия от 19:06, 2 ноября 2024 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Основные результаты) ← Предыдущая правка		Версия от 19:38, 4 ноября 2024 (просмотреть исходный код) Irina (обсуждение \| вклад) (→‎Основные результаты) Следующая правка →
Строка 49:		Строка 49:


	Теорема 2. Предположим, что -^ < ~~e < j~~. Тогда любой рандомизированной схеме с двухсторонней ч-ошибкой, отвечающей на запросы с помощью одного битового зонда, требуется объем памяти &{€\~~0 "ty€~~\ log m).		'''Теорема 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>.'''