Архив метки: probability

Рандом с учетом весов за O(1) — Walker’s alias method

Есть массив A[n] с весами. Нужно выбрать случайный элемент, но не равномерным рандомом, а в соответствии с этими весами. (В общем, это дискретное распределение вероятности) Чем примечателен метод алиаса, так это константным временем выполнения O(1)

Рубрика: Алгоритмы, Программирование, Разное | Метки: , , , | 2 комментария