并集问题的一个随机算法

随机算法由于其简洁和高效的特点正在计算中占据越来越重要的位置.但有时随机算法的优良性能并不要求用完全独立的随机变量作为它的输入.仅用成对独立的随机变量作为输入，得到了一个关于估计并集的基的问题的随机算法.这一方法可以减少随机算法中使用的随机位.对于固定的精确度ε和确信度δ,此算法需要o(t1/2)的随机位，比标准的随机算法所使用的随机位数o(tlogtm)要少得多.而算法的执行时间并没有显著地增加o(t2logm).