Lecture Algorithm design - Chapter 5: Divide and conquer II

Chia sẻ: You Can | Ngày: | Loại File: PDF | Số trang:67

Thêm vào BST

Báo xấu

59
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

The following will be discussed in lecture Algorithm design - Chapter 5: Divide and Conquer II: Master theorem, integer multiplication, matrix multiplication, convolution and FFT. inviting you refer.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lecture Algorithm design - Chapter 5: Divide and conquer II

D IVIDE AND C ONQUER II ‣ master theorem ‣ integer multiplication ‣ matrix multiplication ‣ convolution and FFT Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/~wayne/kleinberg-tardos Last updated on Jul 20, 2015, 3:31 PM
D IVIDE AND C ONQUER II ‣ master theorem ‣ integer multiplication ‣ matrix multiplication ‣ convolution and FFT SECTIONS 4.3-4.6
Master method Goal. Recipe for solving common divide-and-conquer recurrences: n T (n) = a T + f (n) b Terms. ・a ≥ 1 is the number of subproblems. ・b > 0 is the factor by which the subproblem size decreases. ・f (n) = work to divide/merge subproblems. Recursion tree. ・k = logb n levels. ・ai = number of subproblems at level i. ・n / bi = size of subproblem at level i. 3
Case 1: total cost dominated by cost of leaves Ex 1. If T (n) satisfies T (n) = 3 T (n / 2) + n, with T (1) = 1, then T (n) = Θ(nlg 3). T (n) n T (n / 2) T (n / 2) T (n / 2) 3 (n / 2) T (n / 4) T (n / 4) T (n / 4) T (n / 4) T (n / 4) T (n / 4) T (n / 4) T (n / 4) T (n / 4) 32 (n / 22) log2 n 3i (n / 2i) ⋮ ⋮ T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) ... T (1) T (1) T (1) 3log2 n (n / 2log2 n ) 3log2 n = nlog2 3 2 3 log2 n r1+log2 n 1 r=3/2 >1 T (n) = (1 + r + r + r + . . . + r )n = n = 3nlog2 3 2n r 1 4
Case 2: total cost evenly distributed among levels Ex 2. If T (n) satisfies T (n) = 2 T (n / 2) + n, with T (1) = 1, then T (n) = Θ(n log n). T (n) n T (n / 2) T (n / 2) 2 (n / 2) T (n / 4) T (n / 4) T (n / 4) T (n / 4) 22 (n / 22) log2 n T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) 23 (n / 23) ⋮ ⋮ T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) ... T (1) T (1) T (1) n (1) 2log2 n = n r=1 T (n) = (1 + r + r2 + r3 + . . . + rlog2 n ) n = n (log2 n + 1) 5
Case 3: total cost dominated by cost of root Ex 3. If T (n) satisfies T (n) = 3 T (n / 4) + n5, with T (1) = 1, then T (n) = Θ(n5). T (n) n5 T (n / 4) T (n / 4) T (n / 4) 3 (n / 4)5 T (n / 16) T (n / 16) T (n / 16) T (n / 16) T (n / 16) T (n / 16) T (n / 16) T (n / 16) T (n / 16) 32 (n / 42)5 log4 n 3i (n / 4i)5 ⋮ ⋮ T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) ... T (1) T (1) T (1) 3log4 n (n/4log4 n )5 3log4 n = nlog4 3 1 r=3/ 45
Master theorem Master theorem. Suppose that T (n) is a function on the nonnegative integers that satisfies the recurrence n T (n) = a T + f (n) b where n / b means either ⎣ n / b⎦ or ⎡ n / b⎤. Let k = logb a. Then, Case 1. If f (n) = O(nk – ε) for some constant ε > 0, then T (n) = Θ(nk). Ex. T (n) = 3 T(n / 2) + n. ・a = 3, b = 2, f (n) = n, k = log2 3. ・T (n) = Θ(nlg 3). 7
Master theorem Master theorem. Suppose that T (n) is a function on the nonnegative integers that satisfies the recurrence n T (n) = a T + f (n) b where n / b means either ⎣ n / b⎦ or ⎡ n / b⎤. Let k = logb a. Then, Case 2. If f (n) = Θ(nk log p n), then T (n) = Θ(nk log p+1 n). Ex. T (n) = 2 T(n / 2) + Θ(n log n). ・a = 2, b = 2, f (n) = 17 n, k = log2 2 = 1, p = 1. ・T (n) = Θ(n log2 n). 8
Master theorem Master theorem. Suppose that T (n) is a function on the nonnegative integers that satisfies the recurrence n T (n) = a T + f (n) b regularity condition holds where n / b means either ⎣ n / b⎦ or ⎡ n / b⎤. Let k = logb a. Then, if f(n) = Θ(nk + ε) Case 3. If f (n) = Ω(nk + ε) for some constant ε > 0 and if a f (n / b) ≤ c f (n) for some constant c < 1 and all sufficiently large n, then T (n) = Θ ( f (n) ). Ex. T (n) = 3 T(n / 4) + n5. ・a = 3, b = 4, f (n) = n5, k = log4 3. ・T (n) = Θ(n5). 9
Master theorem Master theorem. Suppose that T (n) is a function on the nonnegative integers that satisfies the recurrence n T (n) = a T + f (n) b where n / b means either ⎣ n / b⎦ or ⎡ n / b⎤. Let k = logb a. Then, Case 1. If f (n) = O(nk – ε) for some constant ε > 0, then T (n) = Θ(nk). Case 2. If f (n) = Θ(nk log p n), then T (n) = Θ(nk log p+1 n). Case 3. If f (n) = Ω(nk + ε) for some constant ε > 0 and if a f (n / b) ≤ c f (n) for some constant c < 1 and all sufficiently large n, then T (n) = Θ ( f (n) ). Pf sketch. ・Use recursion tree to sum up terms (assuming n is an exact power of b). ・Three cases for geometric series. ・Deal with floors and ceilings. 10
Akra-Bazzi theorem Desiderata. Generalizes master theorem to divide-and-conquer algorithms where subproblems have substantially different sizes. Theorem. [Akra-Bazzi] Given constants ai > 0 and 0 < bi ≤ 1, functions hi (n) = O(n / log 2 n) and g(n) = O(nc), if the function T(n) satisfies the recurrence: k T (n) = ai T (bi n + hi (n)) + g(n) i=1 ai subproblems small perturbation to handle of size bi n floors and ceilings n k p g(u) ai bpi = 1 . Then T(n) = n 1+ p+1 du where p satisfies 1 u i=1 Ex. T(n) = 7/4 T(⎣n / 2⎦) + T(⎡3/4 n⎤) + n2. ・a1 = 7/4, b1 = 1/2, a2 = 1, b2 = 3/4 ⇒ p = 2. ・h1(n) = ⎣1/2 n⎦ – 1/2 n, h2(n) = ⎡3/4 n⎤ – 3/4 n. ・g(n) = n2 ⇒ T(n) = Θ(n2 log n). 11
D IVIDE AND C ONQUER II ‣ master theorem ‣ integer multiplication ‣ matrix multiplication ‣ convolution and FFT SECTION 5.5
Integer addition Addition. Given two n-bit integers a and b, compute a + b. Subtraction. Given two n-bit integers a and b, compute a – b. Grade-school algorithm. Θ(n) bit operations. 1 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 + 0 1 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 Remark. Grade-school addition and subtraction algorithms are asymptotically optimal. 13
Integer multiplication Multiplication. Given two n-bit integers a and b, compute a × b. Grade-school algorithm. Θ(n2) bit operations. 1 1 0 1 0 1 0 1 × 0 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 Conjecture. [Kolmogorov 1952] Grade-school algorithm is optimal. Theorem. [Karatsuba 1960] Conjecture is wrong. 14
Divide-and-conquer multiplication To multiply two n-bit integers x and y: ・Divide x and y into low- and high-order bits. ・Multiply four ½n-bit integers, recursively. ・Add and shift to obtain result. m = ⎡ n / 2 ⎤ a = ⎣ x / 2m⎦ b = x mod 2m use bit shifting to compute 4 terms c = ⎣ y / 2m⎦ d = y mod 2m (2m a + b) (2m c + d) = 22m ac + 2m (bc + ad) + bd 1 2 3 4 Ex. x = 1 0 0 0 1 1 0 1 y =11100001 a b c d 15
Divide-and-conquer multiplication MULTIPLY(x, y, n) _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ IF (n = 1) RETURN x 𐄂 y. ELSE m ← ⎡ n / 2 ⎤. a ← ⎣ x / 2m⎦; b ← x mod 2m. c ← ⎣ y / 2m⎦; d ← y mod 2m. e ← MULTIPLY(a, c, m). f ← MULTIPLY(b, d, m). g ← MULTIPLY(b, c, m). h ← MULTIPLY(a, d, m). RETURN 22m e + 2m (g + h) + f. _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 16
Divide-and-conquer multiplication analysis Proposition. The divide-and-conquer multiplication algorithm requires Θ(n2) bit operations to multiply two n-bit integers. Pf. Apply case 1 of the master theorem to the recurrence: T (n) = 4T (n /2) + Θ(n) ⇒ T (n) = Θ(n 2 ) !#"# $ !"$ recursive calls add, shift € 17
Karatsuba trick To compute middle term bc + ad, use identity: bc + ad = ac + bd – (a – b) (c – d) m = ⎡ n / 2 ⎤ a = ⎣ x / 2m⎦ b = x mod 2m middle term c = ⎣ y / 2m⎦ d = y mod 2m (2m a + b) (2m c + d) = 22m ac + 2m (bc + ad ) + bd = 22m ac + 2m (ac + bd – (a – b)(c – d)) + bd 1 1 3 2 3 Bottom line. Only three multiplication of n / 2-bit integers. 18
Karatsuba multiplication KARATSUBA-MULTIPLY(x, y, n) _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ IF (n = 1) RETURN x 𐄂 y. ELSE m ← ⎡ n / 2 ⎤. a ← ⎣ x / 2m⎦; b ← x mod 2m. c ← ⎣ y / 2m⎦; d ← y mod 2m. e ← KARATSUBA-MULTIPLY(a, c, m). f ← KARATSUBA-MULTIPLY(b, d, m). g ← KARATSUBA-MULTIPLY(a – b, c – d, m). RETURN 22m e + 2m (e + f – g) + f. _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 19
Karatsuba analysis Proposition. Karatsuba's algorithm requires O(n1.585) bit operations to multiply two n-bit integers. Pf. Apply case 1 of the master theorem to the recurrence: T(n) = 3 T(n / 2) + Θ(n) ⇒ T(n) = Θ(nlg 3) = O(n1.585). Practice. Faster than grade-school algorithm for about 320-640 bits. 20