问是否从有偏差的列表中选择项目？
EN

Stack Overflow用户

提问于 2010-04-09 02:43:11

回答 1查看 148关注 0票数 1

给出一个项目列表x1 ...xn和相关概率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)时间。还有比这更有效的方法吗？

回答已采纳

发布于 2010-04-09 03:03:31

我不认为你真的需要对列表进行排序才能让算法工作。

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)。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/2602533

复制

相似问题

问是否从有偏差的列表中选择项目？EN