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