# 程序代写 COMP90038 – cscodehelp代写

COMP90038
Algorithms and Complexity
Lecture 11: Sorting with Divide-and-Conquer (with thanks to Harald Søndergaard)

DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray

2
Divide and Conquer
We earlier studied recursion as a powerful problem

solving technique.
The divide-and-conquer strategy tries to make the most
1. Divide the given problem instance into smaller
instances.
2. Solve the smaller instances recursively.
3. Combine the smaller solutions to solve the original instance.

of this idea:
This works best when the smaller instances can be made

to be of equal (or near-equal) size.

Split-Solve-and-Join Approach

4
Divide and Conquer Algorithms

We will discuss:
The Master Theorem
Mergesort
Quicksort
Tree traversal Closest Pair revisited
• • • •

Divide-and-Conqer General Case
problem of size n
problem of size n/b
problem of size n/b
problem of size n/b

problem of size n/b
b sub-problems

Divide-and-Conqer General Case
problem of size n
problem of size n/b
problem of size n/b
problem of size n/b

problem of size n/b
only a sub-problems need to be solved

Divide-and-Conqer General Case
problem of size n
problem of size n/b
problem of size n/b
problem of size n/b

problem of size n/b
only a sub-problems need to be solved
combine the a solutions

8
Divide-and-Conquer Recurrences
• •
What is the time required to solve a problem of size n by

divide-and-conquer?
For the general case, assume we split the problem into b

instances (each of size n/b), of which a need to be
solved:
where f(n) expresses the time spent on dividing a problem
into b sub-problems and combining the a results. (A very common case is T(n) = 2T(n/2) + n.)
How to find closed forms for these recurrences?
T(n) = aT(n/b) + f(n)

9
The Master Theorem
(A proof is in Levitin’s Appendix B.)
For integer constants a ≥ 1 and b > 1, and function
f with f(n) ∈ Θ(nd), d ≥ 0, the recurrence T(n) = aT(n/b) + f(n)
(with T(1) = c) has solutions, and
Note that we also allow a to be greater than b. Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
• •

Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1

Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1 a = bd
So, by the Master Theorem, T(n) ∈ Θ(n log n) 11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1

Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 2(2T(n/4) + (n/2)) + n

Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 4T(n/4) + 2(n/2) + n

Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 4(2T(n/8) + n/4) + 2(n/2) + n

Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 8T(n/8) + 4(n/4) + 2(n/2) + n

Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 8(2T(n/16) + n/8) + 4(n/4) + 2(n/2) + n

Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 16T(n/16) + 8(n/8) + 4(n/4) + 2(n/2) + n

Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1

Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) ∈ Θ(n log n)

Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1 a = bd
So, by the Master Theorem, T(n) ∈ Θ(n log n) 21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1

Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 4(4T(n/16) + (n/4)) + n

Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 16T(n/16) + 4(n/4) + n

Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 16T(n/16) + 4(n/4) + n

Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 16(4T(n/64) + n/16) 4(n/4) + n

Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 64T(n/64) + 16(n/16) + 4(n/4) + n

Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 64T(n/64) + 16(n/16) + 4(n/4) + n
(log4 n times)

Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 64T(n/64) + 16(n/16) + 4(n/4) + n
(log4 n times)