CSC3160: Design and Analysis of Algorithms Week 7: Divide and Conquer Instructor: Shengyu Zhang 1
Instructor: Shengyu Zhang 1
Example 1:Merge sort 2
Example 1: Merge sort 2
Starting example Sorting: We have a list of numbers x1,...,xn. We want to sort them in the increasing order. 3
Starting example ◼ Sorting: ❑ We have a list of numbers 𝑥1, … , 𝑥𝑛. ❑ We want to sort them in the increasing order. 3
An algorithm:merge sort Merge sort: Cut it into two halves with equal size. Suppose 2 divides n for simplicity. Suppose the two halves are sorted:Merge them. Use two pointers,one for each half,to scan them, during which course do the appropriate merge. How to sort each of the two halves?Recursively. 4
An algorithm: merge sort ◼ Merge sort: ❑ Cut it into two halves with equal size. ◼ Suppose 2 divides 𝑛 for simplicity. ❑ Suppose the two halves are sorted: Merge them. ◼ Use two pointers, one for each half, to scan them, during which course do the appropriate merge. ❑ How to sort each of the two halves? Recursively. 4
Complexity? Suppose this algorithm takes T(n)time for an input with n numbers. Thus each of the two halves takes T(n/2) time. The merging?0(n) Scanning n elements,an 0(1)time operation needed for each. Total amount of time:T(n)≤2T(n/2)+c·n. 5
Complexity? ◼ Suppose this algorithm takes 𝑇(𝑛) time for an input with 𝑛 numbers. ◼ Thus each of the two halves takes 𝑇(𝑛/2) time. ◼ The merging? 𝑂(𝑛) ❑ Scanning 𝑛 elements, an 𝑂(1) time operation needed for each. ◼ Total amount of time: 𝑇(𝑛) ≤ 2𝑇(𝑛/2) + 𝑐 ∙ 𝑛. 5
How to solve/bound this recurrence relation? ■T(n)≤2T(n/2)+c·n ≤2T(m/4)+c·n/2 ≤4T(n/4)+2c·n ≤2T(n/8)+c·n/4 ≤8T(m/8)+3c·n ≤ ≤nT(n/m)+(ogn)c·n ≤O(n logn): 6
How to solve/bound this recurrence relation? ◼ 𝑇 𝑛 ≤ 2𝑇 𝑛/2 + 𝑐 ⋅ 𝑛 ~~~~~~~~ ≤ 2𝑇(𝑛/4) + 𝑐 ∙ 𝑛/2 ≤ 4𝑇(𝑛/4) + 2𝑐 ∙ 𝑛 ~~~~~~~ ≤ 2𝑇(𝑛/8) + 𝑐 ∙ 𝑛/4 ≤ 8𝑇(𝑛/8) + 3𝑐 ∙ 𝑛 ≤ … ≤ 𝑛𝑇(𝑛/𝑛) + (log 𝑛)𝑐 ∙ 𝑛 ≤ 𝑂(𝑛 log 𝑛). 6
A general method for designing algorithm: Divide and conquer o f Breaking the problem into subproblems that are themselves smaller instances of the same type of problem Recursively solving these subproblems Appropriately combining their answers
A general method for designing algorithm: Divide and conquer ◼ Breaking the problem into subproblems ❑ that are themselves smaller instances of the same type of problem ◼ Recursively solving these subproblems ◼ Appropriately combining their answers 7
Complexity Running time on an input of size n:T(n) Break problem into a subproblems,each of the same size n/b. In general,a is not necessarily equal to b. Time to recursively solve each subproblem: T(n/b) Time for breaking problem (into subproblems) and combining the answers:0(n) 8
Complexity ◼ Running time on an input of size 𝑛: 𝑇(𝑛) ◼ Break problem into 𝑎 subproblems, each of the same size 𝑛/𝑏. ❑ In general, 𝑎 is not necessarily equal to 𝑏. ◼ Time to recursively solve each subproblem: 𝑇(𝑛/𝑏) ◼ Time for breaking problem (into subproblems) and combining the answers: 𝑂(𝑛 𝑑 ) 8
Master theorem ·T(n)=aT(n/b)+O(na) a 0,b>1,and d >0 are all constants. Then O(n m了O3 ifd logb a O(ndlogn) if d logb a ifd<logb a· Proof in textbook.Not required. 口 But you need to know how to apply it. 9
Master theorem ◼ 𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑂(𝑛 𝑑 ) ❑ 𝑎 > 0, 𝑏 > 1, and 𝑑 ≥ 0 are all constants. ◼ Then ❑ Proof in textbook. Not required. ❑ But you need to know how to apply it. 9
■T(n)=aT(n/b)+O(nd) rm二z ifd logb a O(ndlogn) if d logb a if'd logb a. Merge sort:T(n)<2T(n/2)+0(n). a=b=2,d=1.So d=logb a. By the master theorem:T(n)=0(n logn). 10
◼ 𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑂(𝑛 𝑑 ) ◼ Merge sort: 𝑇(𝑛) ≤ 2𝑇(𝑛/2) + 𝑂(𝑛). ◼ 𝑎 = 𝑏 = 2, 𝑑 = 1. So 𝑑 = log𝑏 𝑎. ◼ By the master theorem: 𝑇(𝑛) = 𝑂(𝑛 log 𝑛). 10