实线上间隔的恒定时间隶属度索引？
假设给我一组总和为 1 的重量，我将它们一个接一个地排列起来，形成一系列长度与其重量成正比的箱子。我为每个 bin 分配一个与其在行中的位置相对应的整数。
给定 [0,1] 中的任何数字，我希望能够检查哪个索引对应于该数字所在的 bin。我可以想出一种算法在恒定时间内完成此操作吗？
对数时间解决方案很简单，但我希望有一个更好的解决方案！
Say I were given a set of weights adding up to 1, and I lined them up one after another to make a series of bins with length proportional to their weight. I assign each bin an integer corresponding to its place in line.
Given any number in [0,1], I would like to be able to check which index corresponds to the bin this number lands in. Can I come up with an algorithm to do this in constant time?
A logarithmic time solution is straightforward, but I'm hoping for one better!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这可能可以使用别名方法来完成，该方法可用于生成随机样本来自时间 O(1) 的离散分布。我相信您可以通过简单地反转变换来适应此算法来解决您的问题，这样您就可以从离散存储桶映射到统一变量，而不是从统一随机变量映射到离散存储桶。从那里，您可以确定该值属于哪个存储桶。
希望这会有所帮助！
编辑：我最近写了一篇关于别名方法和其他相关技巧的广泛文章。希望这能让算法及其直觉变得更清晰、更容易！
This can probably be accomplished using the alias method, which can be used to generate random samples from a discrete distribution in time O(1). I believe that you can adapt this algorithm to solve your problem by simply inverting the transform so that instead of mapping from a uniform random variable to a discrete bucket, you map from a discrete bucket to a uniform variable. From there, you can determine which bucket the value falls in.
Hope this helps!
EDIT: I recently wrote an extensive write-up of the alias method and other related tricks. Hopefully this makes the algorithm and its intuition clearer and easier!
创建一个包含 k 个条目的表，并且 1/k 必须小于最小条目。
然后，您将表中的条目填充到它们指向的位置，然后您的时间复杂度为 O(1)。
如果放松对 k 的限制，则可以创建多级查找，其中第一步如上所述，但第二步是线性或对数搜索。这就会变成
O(log2(n/k))。n/k, k=n => O(log2(1)) = O(1) ？要查找表中要使用的条目，它是floor(x*k)
Create a table with k entries and 1/k must be smaller than your smallest entry.
Then you fill the table with entries to where they point to, and then you have O(1).
If you relax the restraint on k, you can create a multistaged lookup, where the first step is as above, but the second step is a linear or logarithmic search. This then becomes a
O(log2(n/k)).n/k, k=n => O(log2(1)) = O(1)?To find which entry in the table to use, it is floor(x*k)