假设我得到了一组总和为 1 的重量，我将它们一个接一个地排列起来，形成一系列长度与其重量成正比的箱子。我为每个 bin 分配一个与其在行中的位置相对应的整数。
给定 [0,1] 中的任何数字，我希望能够检查哪个索引对应于该数字所在的容器。我可以想出一种算法在恒定时间内完成此操作吗？
对数时间解决方案很简单，但我希望有更好的解决方案!
最佳答案
这可能可以使用 alias method 来完成，可用于在时间 O(1) 内从离散分布生成随机样本。我相信您可以通过简单地反转变换来适应此算法来解决您的问题，这样您就可以从离散存储桶映射到统一变量，而不是从统一随机变量映射到离散存储桶。从那里，您可以确定该值属于哪个存储桶。
希望这有帮助!
编辑:我最近写了一篇关于别名方法和其他相关技巧的广泛文章。希望这能让算法及其直觉更加清晰和容易!
关于algorithm - 实线上间隔的恒定时间隶属度索引？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7375094/