方根划分技术 ·算法分析 (1)算法在并行递归过程中所需的处理器数≤k=L√P9 段间比较：VpLV比较对数≤Vp四于k; 段内比较：WP.WG」Dspa上k 递归调用：设A,B分成若干子段对为p1,q1),(P2,q2),· 则∑p:≤p,∑q:≤q,由Cauchy不等式=> ∑Wpa.Js∑p4,sL∑p,∑ns.pa=k 综上，整个过程可用处理器数k=√p西完成。 (2)时间分析 记是第1次递归后的A组最大长度，=>=p,≤V,s…≤p 算法在，=常数C时终止递归，即p”上常数C=>i≤1 og log p+常数C 由(1)知算法中其他各步的时间为O(1),所以Valiant归并算法时间 (p,q)=O(loglogp)p<q 2011/10/25 算法分析 (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 归并算法时间 tk ( p,q)  O(loglog p) p  q 13 2011/10/25 方根划分技术