功能划分技术
划分方法
n个元素A[1..n]分成等长的p组,每组满足某种特性。
示例:(m, n)选择问题(求出n个元素中前m个最小者)
功能划分:要求每组元素个数必须大于m;
算法:p148算法6.4
输入:A=(a1,…,an); 输出:前m个最小者;
Begin
(1) 功能划分:将A划分成g=n/m组,每组含m个元素;
(2) 局部排序:使用Batcher排序网络将各组并行进行排序;
(3) 两两比较:将所排序的各组两两进行比较,从而形成MIN序列;
(4) 排序-比较:对各个MIN序列,重复执行第(2)和第(3)步,直至
选出m个最小者。
End
2022-03-25 00:28:12
8.4MB
并行计算
1