Bic*_*Cao 13 random algorithm hashtable sampling data-structures
仅仅是为了练习(而不是作业),我一直试图解决这个问题(CLRS,第3版,练习11.2-6):
假设我们在大小为m的哈希表中存储了n个密钥,通过链接解决了冲突,并且我们知道每个链的长度,包括最长链的长度L. 描述从散列表中的密钥中随机均匀地选择密钥并在预期时间O(L*(1 + m/n))中返回它的过程.
到目前为止我所想的是每个键返回的概率是1/n.如果我们试图得到一个介于1到n之间的随机值x,并尝试按顺序查找按顺序排序的第x个密钥,然后沿着存储桶中的链,那么将需要O(m)才能找到正确的存储桶通过桶一个接一个地和O(L)时间来获得链中的正确密钥.
ant*_*kos 23
重复以下步骤,直到返回一个元素:
k在斗元素的数量.p从中随机选择1 ... L.如果p <= k然后返回p桶中的th元素.应该清楚的是,该过程随机均匀地返回一个元素.我们将排斥采样应用于放置在2D阵列中的元素.
每桶的预期元素数量是n / m.抽样尝试成功的概率是(n / m) / L.因此,找到存储桶所需的预期尝试次数L * m / n.连同O(L)从桶中检索元素的成本,预期的运行时间是O(L * (1 + m / n)).