假设我得到了一组加起来为 1 的重量，我将它们一个接一个地排成一排，以制作一系列长度与其重量成正比的箱子。我为每个 bin 分配一个与其在行中的位置相对应的整数。
给定 [0,1] 中的任何数字，我希望能够检查哪个索引对应于该数字所在的 bin。我可以想出一个算法来在恒定时间内执行此操作吗？
对数时间解决方案很简单，但我希望有更好的解决方案！
问问题
148 次
2 回答
3
这可能可以使用别名方法来完成，该方法可用于从时间 O(1) 中的离散分布生成随机样本。我相信你可以通过简单地反转变换来调整这个算法来解决你的问题，这样你就可以从一个离散的桶映射到一个统一的变量，而不是从一个统一的随机变量映射到一个离散的桶。从那里，您可以确定该值属于哪个存储桶。
希望这可以帮助！
编辑：我最近写了一篇关于别名方法和其他相关技巧的详尽文章。希望这能让算法及其直觉更清晰、更容易！
于 2011-09-10T22:34:50.727 回答
0
创建一个包含 k 个条目的表，并且 1/k 必须小于您的最小条目。然后你用它们指向的条目填充表格，然后你有 O(1)。
如果放松对k的约束，可以创建多阶段查找，其中第一步如上，但第二步是线性或对数搜索。然后这变成了一个O(log2(n/k)). n/k, k=n => O(log2(1)) = O(1)?
要查找要使用表中的哪个条目，它是 floor(x*k)
于 2011-09-10T22:35:46.330 回答