Выберите элемент из списка с предубеждением?

Question

Учитывая список элементов x1 ... xn и связанных с ними probabilties p1 ... pn, которые суммируются до 1, существует известная процедура выбора случайного элемента с его ассоциированной вероятностью путем сортировки списка по весу, выбора случайного значение между 1 и 0 и суммирование до суммы кульминации до тех пор, пока оно не превысит выбранное значение и не вернет элемент в этот момент.

Итак, если мы имеем x1 -> 0,5, x2 -> 0,3, x3 -> 0,2, если выбрано случайно выбранное значение меньше 0,5 x1, если между 0,5 и 0,8, x2 и еще x3.

Для этого требуется сортировка, поэтому требуется время O (nlogn). Есть ли что-то более эффективное?

Answer 1

Я не думаю, что вам действительно нужно отсортировать список для работы алгоритма.

x1 = 0,2, x2 = 0,7, x3 = 0,1

Если вы как бы то у вас есть:

x3: 0.0 to 0.1 = 10% 
x1: 0.1 to 0.3 = 20% 
x2: 0.3 to 1.0 = 70% 

Если вы не делаете, вы вместо того, чтобы получить:

x1: 0.0 to 0.2 = 20% 
x2: 0.2 to 0.9 = 70% 
x3: 0.9 to 1.0 = 10% 

Просто устранения сортировка и итерация через это сделали бы O (n).