| 可重构造的网孔机器上的k-选择 |
| |
| 引用本文： | 许胤龙,陈国良,万颖瑜.可重构造的网孔机器上的k-选择[J].计算机研究与发展,1999,36(9):1069-1075. |
| |
| 作者姓名： | 许胤龙 陈国良 万颖瑜 |
| |
| 作者单位： | 中国科学技术大学计算机科学技术系国家高性能计算中心,合肥,230027 |
| |
| 摘 要： | 对于一个 ｍ ×ｎ（ｍ ≤ｋ）的列有序矩阵，文中在 ｎ × ｎ 可重构造的网孔机器上提出了一个并行 ｋ选择算法，其时间复杂度为 Ｏ（ｌｏｇ２ｍ ＋ ｌｏｇｍ ｌｏｇ２ ｎ＋ ｌｏｇ３ ｎ），而对于一般的ｌ元集，文中在相同的模型下提出了一个时间复杂度为 Ｏ ｌｏｇ２ ｌｎ ＋ ｌｏｇ ｌｎ ｌｏｇ２ ｎ＋ ｌｏｇ３ｎ＋ ｌｎ ｌｏｇ ｌｎ 的并行 ｋ选择算法．当时 ｌ≥ Ｏ（ｎｌｏｇ３ｎ／ｌｏｇ ｌｏｇｎ，该时间复杂度为 Ｏ ｌｎ ｌｏｇ ｌｎ ．特别地，当ｌ＝ Ｏ（ｎ１＋ ε）（ε＞ ０ 为常数），则时间复杂度为 Ｏ ｌｎ ｌｏｇｎ ．此时达到的加速比为 ｎ／ｌｏｇｎ．
|
| 关 键 词： | 并行算法 k-选择 可重构造 |
k-SELECTION ON RECONFIGURABLE MESH |
| |
| XU Yin-long,CHEN Guo-Liang,WAN Ying-Yu.k-SELECTION ON RECONFIGURABLE MESH[J].Journal of Computer Research and Development,1999,36(9):1069-1075. |
| |
| Authors: | XU Yin-long CHEN Guo-Liang WAN Ying-Yu |
| |
| Abstract: | |
| |
| Keywords: | parallel algorithm k\|selection reconfiguration |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
