03-分治策略全解.ppt

复杂性分析 * 递推关系式 T(n)=O(nlogn) Thanks！ * Choosing the pivot 1. Divide the n elements into groups of 5. Choosing the pivot 2. Find the median of each 5-element group. Choosing the pivot Choosing the pivot Choosing the pivot Choosing the pivot Minor simplification Analysis of Alg. SELECT Running Time T(n)= Θ (n) Conclusions Since the work at each level of recursion is a constant fraction (19/20) smaller, the work per level is a geometric series dominated by the linear work at the root. In practice, this algorithm runs slowly, because the constant in front of n is large. The randomized algorithm is far more practical. * 5 大整数乘法(Large Integer Multiplication) Complex multiplication. (a + bi) (c + di) = x + yi. Grade-school. x = ac - bd, y = bc + ad. Gauss method. x = ac - bd, y = (a + b) (c + d) - ac - bd. Remark. Improvement if no hardware multiply. 4 ultiplications, 2 additions 3 multiplications, 5 additions * Integer Arithmetic Add. Given two n-bit integers a and b, compute a + b. Grade-school. Θ(n) bit operations. Multiply. Given two n-bit integers a and b, compute a * b. Grade-school. Θ(n2) bit operations. * Multiply two n-bit integers x = (10ma +b), y = (10mc +d), m=n/2 x y = (10ma +b) (10mc +d) Example: x = 1234567890, m=5, a=12345, b=67890 Multiply four n/2-bit integers. ac, bc, ad, bd Add and shift to obtain result. x y = 102mac + 10m(bc +ad)+ bd * 分治算法伪代码 Alg. Multiply (x, y, n) If n = 1 return x*y; Else m = n/2; a = x/10m, b = x mod 10m; c = y/10m, d= y mod 10m; e = Multiply(a, c,m); f = Multiply(b, d, m); g = Multiply(b, c, m); h = Multiply(a, d, m); Reutrn 102m*e + 10m* (g+h) +f; * Running Time of Alg. Multiply T(n) = 4T(n/2) + O(n) T(1) = 1 Which solves to T(n) = O(n2) by the master theorem. Fast multiply: Anatolii, Karatsuba in 1962: x y = 102mac + 10m(bc +ad)+ bd T(n) = 3 T(n/2) + O(n) T(n) = O(nlg3)=O(n1.585) bc + ad = ac+ bd - (a - b