复旦大学：《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 02 Divide-and-conquer design paradigm

Data Structures and Algorithm Xiaoqing Zheng Zhengxq@fudan.edu.cn

Data Structures and Algorithm Xiaoqing Zheng zhengxq@fudan.edu.cn

D 1vide-and-conquer design paradigm a 1. Divide the problem(instance)into subproblems a 2. Conquer the subproblems by solving them recursively. d3 Combine subproblem solutions

Divide-and-conquer design paradigm ‡ 1. Divide the problem (instance) into subproblems. ‡ 2. Conquer the subproblems by solving them recursively. ‡ 3. Combine subproblem solutions

Merge sort 口1. Divide: Trivial. a 2. Conquer: Recursively sort 2 subarrays d 3. Combine: Linear-time merge 7(n)=27(n/2)+⊙(n) subproblem work dividing number subproblem and combining slze

Merge sort ‡ 1. Divide: Trivial. ‡ 2. Conquer: Recursively sort 2 subarrays. ‡ 3. Combine: Linear-time merge. T(n) = 2 T(n/2) + Θ(n) subproblem number subproblem size work dividing and combining

Binary search o 1. Divide: Check middle element a 2. Conquer: Recursively search I subarray 口3. Combine: Trivial Example: Find 9 357891215

Binary search ‡ 1. Divide: Check middle element. ‡ 2. Conquer: Recursively search 1 subarray. ‡ 3. Combine: Trivial. Example: Find 9 3 5 7 8 9 12 15

Binary search o 1. Divide: Check middle element a 2. Conquer: Recursively search I subarray 口3. Combine: Trivial Example: Find 9 357891215

Binary search ‡ 1. Divide: Check middle element. ‡ 2. Conquer: Recursively search 1 subarray. ‡ 3. Combine: Trivial. Example: Find 9 3 5 7 8 9 12 15

Binary search o 1. Divide: Check middle element a 2. Conquer: Recursively search I subarray 口3. Combine: Trivial Example: Find 9 357891215

Binary search ‡ 1. Divide: Check middle element. ‡ 2. Conquer: Recursively search 1 subarray. ‡ 3. Combine: Trivial. Example: Find 9 3 5 7 8 9 12 15

Recurrence for binary search 7mn)=(17(mn/2)+e(1) subproblem work dividing number subproblem ana combining size

Recurrence for binary search T( n) = 1 T( n/2) + Θ(1) subproblem number subproblem size work dividing and combining

Recurrence for binary search 7mn)=(17(mn/2)+e(1) subproblem work dividing number subproblem ana combining size a=1.b=2→n0g6=n0 CASE2:f(m)=⊙() T(n)=o(gn)

Recurrence for binary search T( n) = 1 T( n/2) + Θ(1) subproblem number subproblem size work dividing and combining a = 1, b = 2 ⇒ log 0 1 b a n n = = CASE 2: f n( ) (1) = Θ ∴Tn l n () (g ) = Θ

Powering a number Problem: Compute an, wherenE N Naive algorithm: o(n) Divide-and-conquer algorithm ifn is even (n-1)/2(n-1)/2 C a ifn is odd 7(n)=7(m/2)+⊙(1)→7(m)=⊙(gn)

Powering a number Problem: Compute a n, where n ∈ ` Naive algorithm: Θ ( n). Divide-and-conquer algorithm: /2 /2 ( 1)/ 2 ( 1)/ 2 n n n n n a a a aaa − − ⎧⎪ ⋅ = ⎨ ⎪⎩ ⋅ ⋅ if n is even; if n is odd. T( n) = T( n/2) + Θ(1) ⇒ T( n) = Θ (lgn )

Fibonacci numbers Recursive definition: ifn=0 ifn=1 n1+hn2ifn≥2; 012358132134…

Fibonacci numbers 1 2 0 1 n n n F F − − F ⎧ ⎪ = ⎨ ⎪ ⎩ + Recursive definition: if n = 0; if n = 1; if n ≥ 2; 0 1 2 3 5 8 13 21 34 ···