并集问题的一个随机算法

• 作者: 张丕兴 张立宇 朱洪
• 来源期刊: 软件学报
• 学科: 数学
• 关键词: 随机算法 成对独立性 并集 随机位 k-独立性
• 年，卷（期）: 2000,（12）
• 页码范围: 1587-1593
• 页数: 7页
• 分类号: O158
• 字数: 1503字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱洪	复旦大学计算机科学系	29	159	7.0	12.0
2	张立宇	复旦大学计算机科学系	1	1	1.0	1.0
3	张丕兴	复旦大学计算机科学系	1	1	1.0	1.0