Мультипроходный точный детерминированный поиск статистик
Алгоритмы обработки потоковых данных


Что: Лекция
Когда: Воскресенье, 05 октября 2014, 11:15–12:50
Где: ПОМИ РАН

Описание

Мы рассмотрим задачу поиска порядковых статистик в потоке и разберем детерминированные алгоритмы. Алгоритм Мунро-Патерсона находит точный ответ, но использует несколько проходов. При разрешенных $p$ проходах алгоритм использует $O(m^{1 \slash p} \log^{2 - 2 \slash p} m \log n)$ памяти.


Статья Мунро-Патерсона (1980)

Видео