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 ···