A Ao.A A B,o Bo, 1 Bo. 2 B A1.o A1. A1.2A B B.1B12B1,3 A A2. 2A2 B20B21B22B2.3 A.。Aa.1A32|A3.3 B30B31B32B3.3 3.MMD机器上PSRS排序算法描述如下: 输入:长度为n的无序序列,P台处理器,每台处理器有m/p个元素 输出:长度为n的有序序列 n (1)均匀划分:n个元素均匀地划分成p段,每台处理器有m个元素。 (2)局部排序:各个处理器利用串行排序算法,排序m个数。 (3)选择样本:每台处理器各从自己的有序段中选取p个样本元素 (4)样本排序:用一台处理器将所有p2个样本元素用串行排序算法排序之 (5)选择主元:用一台处理器选取p-1个主元,并将其播送给其余处理器。 (6)主元划分:各处理器按主元将各自的有序段划分成p段 (7)全局交换:各处理器将其辖段按段号交换到相应的处理器。 (8)归并排序:处理器使用归并排序将所接收的诸段施行排序 ①试证明:当n≥p3时,上述算法的时间复杂度为O("1ogn) 令w表示P中第j段中的元素数,试证明上述算法在执行过程中,处理器中所积累 的元素数目不会超过2n/p,即∑v< 4.PRAM上对数划分算法描述如下: 输入:两非降有序序列A=(a12…,an),B=(b1…,bn),假定ogm和k(m)=m/kogm均为整数 输出:将A和B划分成(m)对段组(A,B),使得|B=lgm,∑|4|=n,且对于所 有1≤i≤k(m)-1,A和B中的每一个i元素均大于41和B中的每一个元素 (1)f(O)=0;j(k(m)=n- 2 - 0,0 1,0 2,0 3,0 0,1 1,1 2,1 3,1 0,2 1,2 2,2 3,2 0,3 1,3 2,3 3,3 0,0 1,0 2,0 3,0 0,1 1,1 2,1 3,1 0,2 1,2 2,2 3,2 0,3 1,3 2,3 3,3 A A A A B B B B A A A A B B B B A A A A B B B B A A A A B B B B 3．MIMD 机器上 PSRS 排序算法描述如下： 输入：长度为 n 的无序序列，p 台处理器，每台处理器有 n p 个元素 输出：长度为 n 的有序序列 Begin （1） 均匀划分：n 个元素均匀地划分成 p 段，每台处理器有 n/p 个元素。 （2） 局部排序：各个处理器利用串行排序算法，排序 n/p 个数。 （3） 选择样本：每台处理器各从自己的有序段中选取 p 个样本元素。 （4） 样本排序：用一台处理器将所有 p 2 个样本元素用串行排序算法排序之。 （5） 选择主元：用一台处理器选取 p-1 个主元，并将其播送给其余处理器。 （6） 主元划分：各处理器按主元将各自的有序段划分成 p 段。 （7） 全局交换：各处理器将其辖段按段号交换到相应的处理器。 （8） 归并排序：处理器使用归并排序将所接收的诸段施行排序。 End ① 试证明：当 3 n p  时，上述算法的时间复杂度为 ( log ) n O n p 。 ② 令 j wi 表示 Pi 中第 j 段中的元素数，试证明上述算法在执行过程中，处理器中所积累 的元素数目不会超过 2 / n p ，即 1 2 p j i j n w = p   。 4．PRAM 上对数划分算法描述如下： 输入：两非降有序序列 ( ,..., ) A = a1 an , ( ,..., ) B = b1 bn ,假定 log m 和 k(m) = m log m 均为整数 输出：将 A 和 B 划分成 k(m) 对段组 ( , ) Ai Bi ，使得 | Bi |= log m，| Ai | = n ，且对于所 有 1  i  k(m) −1， Ai 和 Bi 中的每一个 i 元素均大于 Ai−1 和 Bi−1 中的每一个元素 Begin （1） j(0) = 0 ； j(k(m)) = n