中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 方根剡分技术 算法分析 (1算法在并行递归过程中所需的处理器数≤k=m」 段间比较:F比较对数≤/m」k 段内比较: pIdqhdslvpg」k 递归调用:设AB分成若干子段对为(P1,q1),(p2q2),… 则∑p≤p,∑q≤q,由 Cauchy不等式=> ∑\P」∑P」L∑n∑k{mk 综上,整个过程可用处理器数k=完成。 (2)时间分析 记入1是第次递归后的A组最大长度,=>=p,… 算法在2=常数C时终止递归,即p上常数C i≤ loglog p+常数C1 由1知算法中其他各步的时间为O(1),所以 Valiant归并算法时间 t(p, q=O(og log p) psq 国家高性能计算中心(合肥 2021/2/19国家高性能计算中心（合肥） 10 2021/2/19 ◼ 算法分析 方根划分技术 (1)算法在并行递归过程中所需的处理器数≤k =  pq 段间比较: p q比较对数≤ pq＝k ； 段内比较:  p（  q－1）  pq＝k 递归调用: 设 A,B 分成若干子段对为(p1,q1), (p2,q2),…… 则∑pi≤p, ∑qi≤q, 由 Cauchy 不等式＝>  p q   p q   p q   pq k  i i   i i   i i  = 综上，整个过程可用处理器数k =  pq完成。 (2)时间分析 记λi是第 i 次递归后的 A 组最大长度，＝>0 = p ,     i i i p −  −   2   1  算法在i = 常数C 时终止递归，即p  C i  常数 − 2 ＝> 1 i  log log p +常数C 由(1)知算法中其他各步的时间为 O(1), 所以 Valiant 归并算法时间 t k ( p,q) = O(log log p) p  q