假设我有一个n面加载的骰子，其中每边k 滚动时都有几率p
k上升。我很好奇是否有好的算法可以静态地存储此信息（例如，用于固定的概率集），以便我可以有效地模拟骰子的随机滚动。

目前，我有一个O（lg
n）解决方案。这个想法是存储一张表，列出所有k的前k个边的累积概率，它们在[0，1）范围内生成一个随机实数，并对该表执行二进制搜索以获取最大的索引，其累积值不大于所选值。我更喜欢这种解决方案，但是运行时没有考虑这些可能性似乎很奇怪。特别是，在极端情况下，一侧总是出现或值均匀分布，尽管我的解决方案仍然需要对数步，但仍可以使用天真方法在O（1）中生成滚动结果。

有人对运行时以某种“自适应”方式解决此问题有任何建议吗？

编辑 ：基于对这个问题的回答，我写了
一篇文章，描述了解决这个问题的许多方法
以及它们的分析。看起来Vose对别名方法的实现为每个模具辊提供了Θ（n）预处理时间和O（1）时间，这确实令人印象深刻。希望这是对答案中包含的信息的有用补充！