采用折叠——展开技术的一种并行排序算法 |
| |
引用本文: | 须德,朱宜学.采用折叠——展开技术的一种并行排序算法[J].北方交通大学学报,1998,22(2):81-88. |
| |
作者姓名: | 须德 朱宜学 |
| |
作者单位: | 北方交通大学电子信息工程学院 |
| |
摘 要: | 给出n×n网孔环接式阵列处理机上的一种并行排序算法,它将n×n阵列上的数据折叠成n×n/k子阵列,排序后再展开到整个n×n阵列上,实现n×n项数据的行主序排序,其平均时间复杂度为(2+1/k)n+o(n)。若采用n×n/k阵列模型,且各处理器初始、结束状态允许有k项数据时,该算法的平均时间复杂度只有(1+2/k)n+o(n)。
|
关 键 词: | 网孔环接式 阵列处理机 并行排序算法 折叠 展开 |
本文献已被 维普 等数据库收录! |
|