值的恆定時間分組

假設我有一個值的向量，它表示分類（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

值的恆定時間分組

回答

相關問題