假设我有一个n边加载模,其中每边k都有一些概率PK,当我滚动它的时候。我很好奇是否有一个好的算法来静态地存储这个信息(例如,一个固定的概率集),这样我就可以有效地模拟一个随机的模具辊。
目前,我有一个O(LG N)解决这个问题。其思想是存储所有k的第一个k边的累积概率表,它们在[0,1]范围内生成一个随机实数,并对该表执行二进制搜索,得到累积值不大于所选值的最大索引。我相当喜欢这个解决方案,但运行时没有考虑到这些可能性似乎很奇怪。特别是,在一边总是出现或数值均匀分布的极端情况下,可以使用朴素方法生成O(1)中的滚动结果,尽管我的解决方案仍将采取对数的许多步骤。
有没有人对如何在运行时以某种“自适应”的方式解决这个问题有任何建议?
发布于 2018-03-29 10:06:06
使用平衡的二进位搜索树(或数组中的二进制搜索)并获得O(Logn)复杂度。为每个死掉结果设置一个节点,并将键作为触发该结果的间隔。
function get_result(node, seed):
if seed < node.interval.start:
return get_result(node.left_child, seed)
else if seed < node.interval.end:
// start <= seed < end
return node.result
else:
return get_result(node.right_child, seed)
这个解决方案的好处是实现非常简单,但仍然具有很好的复杂性。
https://stackoverflow.com/questions/-100007854
复制相似问题