| Что: | Лекция |
| Когда: | Воскресенье, 05 октября 2014, 11:15–12:50 |
| Где: | ПОМИ РАН |
Мы рассмотрим задачу поиска порядковых статистик в потоке и разберем детерминированные алгоритмы. Алгоритм Мунро-Патерсона находит точный ответ, но использует несколько проходов. При разрешенных $p$ проходах алгоритм использует $O(m^{1 \slash p} \log^{2 - 2 \slash p} m \log n)$ памяти.
