Введение. Кассовая и турникетная модели. Рассмотрим задачу поиска частых элементов. Дано $k$ и последовательность из $m$ чисел. Мы построим двух-проходный алгоритм (Мисра-Граеса), который находит все элементы, встречающиеся в последовательности хотя бы $\lfloor \frac{m}{k} \rfloor + 1$ раз, и использует $O(k(\log m + \log n))$ памяти. Также покажем нижнюю линейную оценку на память для одно-проходной версии задачи.

Статья Мисра-Граеса (1982)