Введение. Детерминированный поиск частых элементов

Воскресенье, 14 сентября 2014, 11:15–12:50
ПОМИ РАН

Приложенные файлы

Описание

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


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