Метод псевдонима Уокера может рисовать выборку за постоянное наихудшее время, используя несколько вспомогательных массивов размера n, которые необходимо предварительно вычислить. Этот метод описан в главе 3 книги Деврой по сэмплированию и реализован в функции R sample (). Вы можете получить код из исходного кода R или этой ветки . Бумага 1991 от Vose претендует на снижение стоимости инициализации.
Обратите внимание, что ваш вопрос не является четко определенным, если вы не укажете точную форму ввода и сколько случайных чисел вы хотите нарисовать. Например, если входные данные представляют собой массив, дающий вероятность каждого результата, тогда ваш алгоритм не является O (log n), потому что он требует сначала вычисления кумулятивных вероятностей, что занимает O (n) времени из входного массива.
Если вы намереваетесь взять много образцов, тогда стоимость создания одного образца не так важна. Вместо этого важна общая стоимость генерации m результатов и требуемая пиковая память. В связи с этим метод псевдонимов очень хорош. Если вы хотите сэмплировать все сразу, используйте алгоритм O (n + m), опубликованный здесь , а затем перемешайте результаты.