Topic 4: Divide-and-Conquer, Recurrence
Divide & Conquer: MergeSort (CLRS p30-37)
Solving Recurrence Relations (iterated substitution, recurrence tree,
guess and test) (CLRS p83-92)
Copyright By PowCoder代写 加微信 powcoder
Solving Recurrences (Cont’d) Master Theorem (CLRS p.93-97)
Divide and Conquer and recursive programs
A useful design technique for algorithms is divide-and-conquer
These algorithms are often recursive and consist of the following
three steps: Divide:
If the input size is very small (base case) then solve the problem using a simple method.
else, divide the input into two or more disjoint (smaller) pieces & recursively solve the subproblems
Conquer: Leverage on the solutions for the subproblems to get a solution for the original problem.
To analyze (the running time of) a recursive program we express their running time as a recurrence
We then solve the recurrence to find a closed form for the running time of the algorithm.
Topic 4: Divide-and-Conquer, Recurrence
Topic 4: Divide-and-Conquer, Recurrence
lo ≤ mid ≤ hi
A[lo, mid] and A[mid + 1, hi] sorted
A[lo, hi] sorted
Merge runs in O(n) time; the details are not particularly relevant here.
Merge-Sort(A; lo, hi) if lo < hi then
mid = ⌊(lo + hi)/2⌋ Merge-Sort(A; lo, mid) Merge-Sort(A; mid + 1, hi) Merge(A; lo, mid, hi)
Merge-Sort
Merge(A; lo, mid, hi) **pre-condition:
**pre-condition:
**post-condition:
Topic 4: Divide-and-Conquer, Recurrence
Merge sort, the big idea — divide-and-conquer:
Divide the whole list into 2 sublists of equal size; Recursively merge sort the 2 sublists;
Combine the 2 sorted sublists into a sorted list.
An example:
1 2 3 4 5 6 7 8 9 10 11 12 13
A [31 23 01 17 19 28 09 03 13 15 22 08 29]
Merge sort — Example:
Topic 4: Divide-and-Conquer, Recurrence
31 23 01 17 19 28 09 03 13 15 22 08 29
31 23 01 17 19 28 09
03 13 15 22 08 29
31 23 01 17
01 17 23 31
01 09 17 19 23 28 31
03 08 13 15 22 29
01 03 08 09 13 15 17 19 22 23 28 29 31
Recurrence relations — merge sort analysis
MergeSort:
Divide the whole list into 2 sublists of equal size; recursively sort each
Merge the 2 sorted sublists into a sorted list.
Let T (n) denote #KC (# of key comparisons) for a list of size n Assumptions:
n (number of keys in the whole list) is a power of 2;
This makes the analysis easier (since each time we are dividing by 2)
Deriving recurrence relation:
Merge sort on 2 sublists 2 × T(n2 )
Assembling needs n − 1 KC (in WC, the worst case) (it actually takes
n KC; but the code can be easily revised so that n − 1 KC would be sufficient)
0 , ifn=1 T(n)= (n−1)+2·T(n2) , otherwise
How to solve this?
Topic 4: Divide-and-Conquer, Recurrence
Recurrence relations
How to analyze Merge-Sort or any other recursive program?
Write the running time as a recursive function of input size
Recurrence relation: A relation defined recursively — in terms of itself, e.g.,
1, if n = 1 f(n)= n+f(n−1), ifn≥2
Must have base case and general case.
They arise in the analysis of Divide-and-Conquer algorithms
How are recurrences solved?
1. iterated substitution/replacement method 2. recurrence tree method
3. Guess and Test method
4. master theorem method
Topic 4: Divide-and-Conquer, Recurrence
1- Iterated Substitution
1, if n = 1 Consider a simple example f(n) = n+f(n−1), if n ≥ 2
Particular cases: n1234567
f(n) 1 2+1 3+3 4+6 5+10 6+15 7+21 1 3 6 10 15 21 28
General case:
f(n) = n+f(n−1)
= n+(n−1)+f(n−2)
= n+(n−1)+(n−2)+f(n−3)
= n+(n−1)+(n−2)+(n−3)+f(n−4) = ...
= n+(n−1)+(n−2)+(n−3)+...+2+f(1) n
Therefore, we guess that f(n) = i i=1
This is NOT a proof, yet. We prove our guess by induction.
Topic 4: Divide-and-Conquer, Recurrence
Iterated substitution: example (cont’d)
Prove that f(n) = i by induction. i=1
Basecase: n=1. f(1)=1bydefinition,and1i=1i=1.
Inductive step:
Assume f(k) = i, for some natural k ≥ 1. Want to show i=1
f (k + 1) = i by using the recurrence relation (only).
i=1 f(k+1)=(k+1)+f(k)=(k+1)+i= i.
f(n) = i = n(n+1),n ≥ 1.
k k+1 i=1 i=1
Topic 4: Divide-and-Conquer, Recurrence
i=1 Proof by induction (exercise).
n(n+1) is the closed form for the recurrence. 2
You NEED to get the closed forms, as simple as possible!
Recurrence relations — merge sort analysis
Merge sort recall:
Divide the whole list into 2 sublists of equal size;
Recursively merge sort the 2 sublists;
Combine the 2 sorted sublists into a sorted list. Assumptions:
n is a power of 2, which makes the analysis easier (since each time we are dividing by 2)
Let T(n) denote #KC for a list of size n Deriving recurrence relation:
Merge sort on 2 sublists 2 × T(n2 )
Assembling needs n − 1 KC (in the WC)
0 , ifn=1 T(n)= (n−1)+2·T(n2) , otherwise
Solving recurrence relation:
Topic 4: Divide-and-Conquer, Recurrence
Topic 4: Divide-and-Conquer, Recurrence
Merge sort analysis — solving the recurrence relation
Particular case: T(1) = 0,
T(2) = 1, ...
General case:
T(n) = (n−1)+2×T(n)
2 = (n−1)+2× (n2 −1)+2×T(n4)
Solving Merge Sort (Cont’d)
We assume n=2k so:
T(2k) =(2k−1)+2×T(2k−1)
−1)+2×(2k−1 −1)+2×T(2k−2)
−1)+(2k −2)+22 ×T(2k−2)
−1)+(2k −2)+22 ×(2k−2 −1)+2×T(2k−3) −1)+(2k −2)+(2k −22)+23 ×T(2k−3)
−20)+(2k −21)+(2k −22)+23 ×T(2k−3)
−20)+(2k −21)+(2k −22)+(2k −23)+24 ×T(2k−4)
−20)+(2k −21)+(2k −22)+...+(2k −2k−1)+2k ×T(2k−k) −20)+(2k −21)+(2k −22)+...+(2k −2k−1)
= k×2k−k−12i
= (k−1)2k +1 byapplyingk−12i =2k −1
1. Variable substitution makes guessing easy ...
2. In recurrence solving always assume n being some power whenever
necessary (ignore floor and ceiling).
3. Prove by induction.
4. Need to transform back to original variable.
Since n = 2k, we have k = lgn. So, T(n) = n(lgn−1)+1.
Topic 4: Divide-and-Conquer, Recurrence
Closed form proof by induction:
0 if n = 1 Recurrence: T(n)= (n−1)+2×T(n2) if n≥2 Guessedclosedform: T(n)=n(lgn−1)+1,n≥1
Assumingn=2k,k≥0
Basecase: T(1)=0andindeed1(lg(1)−1)+1=0.
Inductive step: Assuming that T(2k) = 2k(k − 1) + 1, k ≥ 0, want to show T(2k+1) = 2k+1k + 1.
By recurrence relation,
T(2k+1) = (2k+1 − 1) + 2 × T(2k)
= (2k+1 −1)+2k+1(k−1)+2
= k2k+1+1.
Extending to n which isn’t a power of 2 is just tedious: if n is not a powerof2,∃integerks.t. n≤2k <2n. So: T(n)≤T(2k)= 2k(k−1)+1 ≤ (2n)·(lg(2n)−1)+1 = 2nlg(n)+1 = O(nlog(n)).
Topic 4: Divide-and-Conquer, Recurrence
Running Time Analysis:
We now wish to deduce that WC running time is Θ(n log n)
Which direction is obvious?
Lower bound: if each KC takes one “unit of time” then our running time is
n(lg(n)−1)+1 ≥ 12nlg(n) ∈ Ω(nlg(n))
Upper bound: Merge takes O(n) times. So ∃c1 such that its running
time ≤ c1n.
Merge-Sort takes O(1) time in the base case and O(1) for the two
recursive calls to make.
Hence, if R(n) denotes the running time of Merge-Sort on n-size input, we have
c3, if n = 1 R(n)= c1·n+c2+2R(n2), ifn≥2
Set C to be any number ≥ c1 + c2 + c3 and we get C, if n = 1
R(n) ≤ Cn + 2R(n2 ), if n ≥ 2 and this recursion solves to
C · n(lg(n)).
Conclusion: merge sort WC running time is Θ(n log n).
Topic 4: Divide-and-Conquer, Recurrence
Conclusions
Divide-and-conquer algorithm often recursive
Analysis of recursive algorithm =⇒ solving recurrence An exercise:
Examine the running time of QZ(n) Proc QZ(n)
if n>1 then
a = n × n + 37
b = a × QZ( n2 )
return QZ(n2)×QZ(n2)+n
return n×n
If we only consider arithmetic operations then: 1 if n = 1
T(n)= 3QZ(n2)+5 ifn≥2
Again, we use Iterated Substitution to obtain a proper guess
Then we prove our guess by induction
Topic 4: Divide-and-Conquer, Recurrence
Exercise (Cont’d):
For simplicity, assume n is a power of 2, say n = 2k:
= 32 ×T(2k−2)+3×5+5
= 32 ×3×T(2k−3)+5+3×5+5
= 33 ×T(2k−3)+32 ×5+3×5+5
= 3k ×T(2k−k)+3k−1 ×5+3k−2 ×5+…+3×5+5
= 3k+5×k−13i i=0
= 3k+5×3k−1 2
= 3.5×3k−2.5
So, our guess is: T(n) = 3.5×3logn −2.5 = 3.5×nlog3 −2.5.
3×T(2k−1)+5
= 3×3×T(2k−2)+5+5
Topic 4: Divide-and-Conquer, Recurrence
Exercise (Cont’d):
Next, prove T(2k) = 3.5 × 3k − 2.5, for k ≥ 0, by induction
Basestep: k=0andT(20)=1=3.5−2.5.
Inductive step: Assume that T (2k−1 ) = 3.5 × 3k−1 − 2.5. By recurrence relation
T(2k) = 3×T(2k )+5 = 3×T(2k−1)+5, 2
T(2k) = 3× 3.5×3k−1 −2.5 +5 = 3.5×3k −2.5.
Thus, it holds for inductive step too.
Therefore, T(2k) = 3.5×3k −2.5 holds for any k ≥ 0.
Topic 4: Divide-and-Conquer, Recurrence
2- Recurrence Tree
Another method to solve a recurrence (and analyze the running time of a recursive program)
Not as formal as iterated substitution; more visual
Consider the Merge-Sort and the tree for the recursive calls of it:
(1,n2) (n2 +1,n)
(1, n) (n +1, n)(n +1, 3n) (3n +1,n) 442244
(1,2) (3,4) …… (n−1,n)
(1,1) (2,2) (3,3) (4,4) (n−1,n−1) (n,n) Question: the number of KC per cell?
Topic 4: Divide-and-Conquer, Recurrence
Merge sort recursion tree (KC per cell):
Assuming merge(n) takes ∼ n KC:
(1,n2) (n2 +1,n)
(1, n) (n +1, n) (n +1, 3n) (3n +1,n) 442244
level 1: n
level 2: n
Topic 4: Divide-and-Conquer, Recurrence
level 3: n ……… …
(1,2) (3,4) …… (n−1,n)
(1,1) (2,2) (3,3) (4,4) (n − 1,n − 1) (n,n)
Where k = log n.
total: kn Therefore, the running time of Merge-Sort is (as found before):
Θ(n log n).
Note: the recurrence tree method is not as applicable nor as formal as the iterated substitution.
level k: n
level k + 1: 0
3- Guess and Test method:
First make a guess for the closed form of the recurrence
Guess can come from the iterated substitution, recurrence tree, or previous experiences
But regardless of the method, your guess must be verified!
Prove the guess by induction
May have to change the guess if the inductive proof fails
Example: Find a closed form for T(n2)+2T(n4)+2n ifn≥4
T (n) = n if 1 ≤ n ≤ 3
Solution: We guess that T (n) ∈ Θ(n log n)
Need to show that there are constants c, d > 0 and naturals n0 , n1 such that:
(i) T(n) ≤ cnlogn for any n ≥ n0, and (ii) T(n) ≥ dnlogn for any n ≥ n1.
We use inductive reasoning to help us find these constants.
Topic 4: Divide-and-Conquer, Recurrence
Topic 4: Divide-and-Conquer, Recurrence
(i) Base case: Let’s consider n0 = 4 to see if it can work.
T(4) = T(2)+2T(1)+8 = 2+2+8 = 12 so T(4) ≤ c·4·lg(4) = 8c for c ≥ 12/8 = 3/2.
AssumeT(i)≤cilogiforallvaluesofi
Let T(n) be defined on nonnegative integers by the recurrence
T(n) = aT(nb ) + f(n).
Then T(n) has the following asymptotic bounds:
1. If f(n) ∈ O(nlogb a−ε), for some ε > 0 then T(n) ∈ Θ(nlogb a).
2. Iff(n)∈Θ(nlogbalogkn)forsomek≥0then
T (n) ∈ Θ(nlogb a logk+1 n),
3. If f(n) ∈ Ω(nlogb a+ε) for some constant ε > 0, and if
af(nb ) ≤ δf(n) for some constant δ < 1 and all sufficiently large n, then T(n) ∈ Θ(f(n)).
Topic 4: Divide-and-Conquer, Recurrence
Some examples:
1 if n = 1
1. T(n)= 7T(n2)+n2 if n≥2
a=7,b=2,f(n)=n2 ⇒logba=log27>2.8,sof(n)∈O(nlog7−0.1) and T(n) ∈ Θ(nlog 7)
1 if n ≤ 2
2. T(n)= 14T(n3)+n3 if n≥3
a = 14,b = 3,f(n) = n3 ⇒ logb a = log3(14) ∈ (2,3), since f(n)∈Ω(nlog3(14)+ε)forε=3−log3(14),and14n3≤14n3 (i.e.with
δ = 2/3 in case 3) T(n) ∈ Θ(n3)
1 if n = 1
3.T(n)= 2T(n2)+n ifn≥2
a=2,b=2,f(n)=n,sincenlogba =n=f(n),wehave f(n) ∈ Θ(nlog2 2) and so (by case 2) T(n) ∈ Θ(nlogn).
1 if n = 1 4.T(n)= 5T(n2)+n2logn ifn≥2
a=5,b=2,f(n)=n2logn. Sologba=log5>2.3,so f(n) ∈ O(nlog 5−0.1) and T(n) ∈ Θ(nlog 5)
Topic 4: Divide-and-Conquer, Recurrence
Master Theorem doesn’t always apply:
ifn≥2 if n = 1
4T(n)+ n2 2 log n
Topic 4: Divide-and-Conquer, Recurrence
a = 4, b = 2, logb a = 2
f(n)= n2 ∈/Θ(n2);
f(n)= n2 ∈O(n2)butf(n)= n2 ∈/O(n2−ε)foranyε>0.
log n log n
What can we do to get the closed form? — iterated substitution!
= 4×T(2k−1)+22k
Topic 4: Divide-and-Conquer, Recurrence
= 42 ×T(2k−2)+4× 22(k−1) + 22k
k−1 k = 42×T(2k−2)+22k +22k
= 43 ×T(2k−3)+42 × 22(k−2) + 22k + 22k k−2 k−1 k
= 43×T(2k−3)+22k +22k +22k
k−2 = 4k×T(1)+ 22k
k−1 k +…+22k +22k
= 4k×T(1)+22k1 +1 +1 +…+1
= 4k ×T(1)+4k ×H(k)
(Harmonicseries: H(n)=1+12 +13 +…+n1=lnn+O(1)=Θ(logn),
CLRS p.1147).
Therefore, T (n) = n2 × T (1) + n2 × H(log n) ∈ Θ(n2H(log n)). Further we have H(k) ∈ Θ(log k) (in fact H(k) = ln k + Θ(1)), thus T(n) ∈ Θ(n2H(logn)) = Θ(n2 loglogn).
k−1 k 123 k
An exercise — dealing with floor & ceiling:
T(n)= T(⌈n2⌉)+1, ifn≥2
Examine some small cases: T (1) = 1
T (3) = T (4) = 3
T (5) = T (6) = T (7) = T (8) = 4
Guess: T(n)=k+1,forany2k−1