На чём держится
журнал
Статьи
SYS
Алгоритм
Резервуарная выборка
k случайных элементов из потока неизвестной длины за один проход и O(k) памяти.
O(n)
2 задачи
RND
Приём
Лас-Вегас и Монте-Карло
Всегда верный, но иногда долгий против всегда быстрого, но иногда неверного — и как превратить одно в другое.
O(k · стоимость одной попытки)
2 задачи
Задачи
Часто рядом
собеседования 2 выборка 1 потоковая обработка 1 случайные числа 1 куча 1 аналитика 1 в проде 1 случайность 1 вероятностная структура 1 оценка 1 матрица 1 многочлены 1