Архив метки: walker’s alias

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