可重构造的网孔机器上的k-选择

• 作者: 万颖瑜 许胤龙 陈国良
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 并行算法 k-选择 可重构造
• 年，卷（期）: 1999,（9）
• 所属期刊栏目: 并行计算
• 页码范围: 1069-1075
• 页数: 7页
• 分类号: TP301.6|TP338.6
• 字数: 4788字
• 语种: 中文

摘要

对于一个m×n(m≤k)的列有序矩阵,文中在()×()可重构造的网孔机器上提出了一个并行k-选择算法,其时间复杂度为O(log2m+logmlog2n+log3n),而对于一般的l元集,文中在相同的模型下提出了一个时间复杂度为O(log2()+()log()log2n+log3n+log())的并行k-选择算法.当时l≥O(nlog3n/log logn,该时间复杂度为O(log()).特别地,当l=O(n1+ε)(ε＞0为常数),则时间复杂度为O(()logn).此时达到的加速比为n/logn.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈国良	中国科学技术大学计算机科学技术系国家高性能计算中心	123	2142	20.0	43.0
2	许胤龙	中国科学技术大学计算机科学技术系国家高性能计算中心	37	259	8.0	14.0
3	万颖瑜	中国科学技术大学计算机科学技术系国家高性能计算中心	5	16	2.0	3.0