Минимальный набор из тервера. 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)