Минимальный набор из тервера. 2-независимые хэш-функции. Задача подсчета различных элементов в потоке. Алгоритм Флажолета-Мартина по версии Алона-Матиаса-Сзегеди (AMS'99). Считает ответ с фиксированной погрешностью и вероятностью ошибки не более \(\delta\). Использует \(O(\log \frac{1}{\delta} \log n)\) памяти. Алгоритм BJKST'04 считает ответ с мультипликативной погрешностью \(\epsilon\) и вероятностью ошибки не более \(\delta\). У нас будет \(O(\log \frac{1}{\delta} \log n)\). Можно довести до \(O(\log n + \log \frac{1}{\delta} (\log \frac{1}{\epsilon} + \log \log n))\).
Статья Флажолета, Мартина (1983)
Статья Алона, Матиаса, Сзегеди (1999)
Статья BJKST (2004)