值的恒定时间分组

假设我有一个值的向量，它表示分类（bin）值的类的上边界。矢量{1,3,5,10}表示箱[0,1 [，[1,3]，[3，5 [和[5,10]。如何在常量时间内对这些类中的一个（0,1,2,3）实现随机值V的分类？一旦V超过垃圾箱的上限，走边界清单并停止，这是微不足道的;但是这是O（n）和箱子的数量;我期待在不变的时间做到这一点。值的恒定时间分组

我以为在实际输入代码之前，通过设置一个查找表，将每个V除以某个值（取决于类边界），然后使用该分割的（圆角）结果来查找在查找表中的bin号码。但是我发现它比我想象的要难得多，尽量使查找表的大小尽可能小，同时仍然准确，无论bin边界之间的比例距离如何;并以一种适用于所有实际价值的方式。通过Google，我只能找到确定垃圾箱边界的算法，至少使用我所做的术语。

来源

2017-04-13 Roel

如果这实际上是一个关于随机抽样的问题，请在Google中搜索别名方法。 –

我刚刚得知倒转方括号也表示排除元素。看看它们是否像这样彼此相邻是相当痛苦的（与[0,1]相比，这意味着相同）。 – Dukeling

我怀疑有一种方法可以在严格恒定的时间内（而不需要无限空间）做到这一点，而不会利用给定数字的某些属性。

查找表是一个体面的想法，但浮点值使这很困难。如果位数是有限的，则可以考虑将查找表表示为本质上为trie（每个级别代表数字的树）。

所以对于{1, 2.5, 5, 9}，你的树会是这个样子：

       root 
//  /  /| \ \ \ \ \ 
0 1   2   3 4 5 6 7 8 9 
     / |  \ 
     2.0 ... 2.5 ... 2.9

每个叶节点将包含指示值区间属于，所以
0将被设置为0，
1 ，2.0 - 2.4都将被设定为1，
2.5 - 2.9，3 - 4将被设置为2，
5 - 9将被设置为3

查询只想involv e从根开始，并重复进入与我们查找的数字中的下一个数字相对应的子节点（如果在上述树中查找2.65，则首先转到2，然后是2.6，那么，因为它是叶，你停止并返回它的值，这是1）。

查询的时间复杂度为O(d)，其中d是向量中有效位数，空间复杂度为O(nd)。

这也许听起来没有特别有效的，但请记住，d是数字数量 - 例如，这将是与m为最大可能值，如果我们谈论的正整数。

O(log n)是相当平凡的，如果你只是建立包含映射到其原来的指数向量所有值binary search tree（BST）。

查找看起来与您如何搜索BST非常相似 - 从根开始并向左或向右移动，直到找到值，除非在这种情况下您记录了您访问的每个节点并返回映射的索引的最接近的值不大。一些API的方法基本上为你做了这些（例如C++中的std::map）。

来源

2017-04-13 17:43:28 Dukeling

我认为获得O（1）的唯一方法是创建一个查找表，以便您可以直接查找所有值。

预期的数字是整数或边界是整数或有限精度：

这如果边界表现很好只是feasable。这使您可以在检查查找表之前对数字进行四舍五入，并大幅减少表中所需的条目。
最大和最小边界之间的差别不能太大。假设我们知道边界的精度是0.5，最小值是1，最大值是10，那么查找表需要（10-1）/0.5 = 18个条目。

对于第一和最后一组（除分钟小于MAX以及更大）的检查用简单做，如果检查哪些不影响的复杂性。

来源

2017-04-13 18:10:13 maraca

值的恒定时间分组

回答

相关问题