代写 algorithm COMP90038
 Algorithms and Complexity

COMP90038
 Algorithms and Complexity
Lecture 10: Decrease-and-Conquer-by-a-Factor
 (with thanks to Harald Søndergaard)
Toby Murray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray

2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Decrease-and-Conquer
Last lecture: to solve a problem of size n, try to express the solution in terms of a solution to the same problem of size n−1.
A simple example was sorting: To sort an array of length n,


just:

1. sort the first n − 1 items, then
2. locate the cell A[j] that should hold the last item, right-shift all elements to its right, then place the last element in A[j].
This led to an O(n2) algorithm called insertion sort. We can implement the idea either with recursion or iteration (we chose iteration).

3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Decrease-and-Conquer
 by-a-Factor
We now look at better utilization of the approach, often leading to methods with logarithmic time behaviour or better!

Decrease-by-a-constant-factor is exemplified by Decrease-by-a-variable-factor is exemplified by

binary search.

interpolation search.

Let us look at these and other instances.

Binary Search
This is a well-known approach for searching for an element k Start by comparing against the array’s middle element A[m].
If A[m] > k, search the sub-array up to A[m − 1] recursively. If A[m] < k, search the sub-array from A[m + 1] recursively. • in a sorted array. • If A[m] = k we are done. • • 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Binary Search We have already seen a recursive formulation in • Lecture 4. Here is an iterative one. 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:
 Binary Search in Sorted Array A: 0123456 k: 41 lo: 0 hi: 6 m: 3 4 9 13 22 41 83 96 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License BinSearch(A,7,41) Example:
 Binary Search in Sorted Array A: 0123456 k: 41 lo: 4 hi: 6 m: 3 4 9 13 22 41 83 96 7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License BinSearch(A,7,41) Example:
 Binary Search in Sorted Array A: 0123456 k: 41 lo: 4 hi: 6 m: 5 4 9 13 22 41 83 96 8 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License BinSearch(A,7,41) Example:
 Binary Search in Sorted Array A: 0123456 k: 41 lo: 4 hi: 4 m: 5 4 9 13 22 41 83 96 9 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License BinSearch(A,7,41) Example:
 Binary Search in Sorted Array A: 0123456 k: 41 lo: 4 hi: 4 m: 4 4 9 13 22 41 83 96 10 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License BinSearch(A,7,41) Complexity of Binary Search • • Worst-case input to binary sarch: When k is not in the array In that case, its complexity is given by the following • recursive equation:
 11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License • 
 A closed form is: • The average-case time complexity is also Θ(log n) In the worst case, searching for k in an array of size • 1,000,000 requires 20 comparisons. Russian Peasant 
 Multiplication A way of doing multiplication. For even n:
 • • For odd n:
 n−1 
 n⋅m= 2 ⋅2m+m nm 
 n ⋅ m = n ⋅ 2m 81 92 92 2 40184 • 20 368 10 736 Thus, ~halve n repeatedly, until
 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License • n = 1. Add up all odd values of m 1 5888 5888 = 7452 5 1472 1472 2 2944 12 Finding the Median Given an array, an important problem is how to find the median, that is, an array value which is no larger than half the elements and no smaller than half. A: • 9 23 3 41 22 8 46 0123456 More generally, we would like to solve the problem of finding the kth • smallest element. (e.g. when k=3) 9 23 3 41 22 8 46 A: 0123456 If the array is sorted, the solution is straight-forward, so one approach is to • start by sorting (as we’ll soon see, this can be done in time O (n log n)).
 
 0123456 However, sorting the array seems like overkill. 3 8 9 22 23 41 46 13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License • A: A Detour via Partitioning Partitioning an array around some pivot element p means reorganizing the array so that all elements to the left of p are no greater than p, while those to the right are no smaller. A: 0123456 Partitioning around the pivot 9 A: 0123456 • 9 23 3 41 22 8 46 3 8 9 23 22 41 46 14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Lomuto Partitioning lo hi 0123456 si 9 23 3 41 22 8 46 15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Lomuto Partitioning lo hi 0123456 si 9 23 3 41 22 8 46 16 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Lomuto Partitioning lo hi 0123456 si 9 23 3 41 22 8 46 17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Lomuto Partitioning lo hi 0123456 si 9 3 23 41 22 8 46 18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Lomuto Partitioning lo hi 0123456 si 9 3 23 41 22 8 46 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Lomuto Partitioning lo hi 0123456 si 9 3 23 41 22 8 46 20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Lomuto Partitioning lo hi 0123456 si 9 3 23 41 22 8 46 21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Lomuto Partitioning lo hi 0123456 si 9 3 23 41 22 8 46 22 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Lomuto Partitioning lo hi 0123456 si 9 3 8 41 22 23 46 23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Lomuto Partitioning lo hi 0123456 si 9 3 8 41 22 23 46 24 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Lomuto Partitioning lo hi 0123456 s 9 3 8 41 22 23 46 25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Lomuto Partitioning lo hi 0123456 s 8 3 9 41 22 23 46 26 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Finding the kth-smallest Element lo hi 0123456 s 8 3 9 41 22 23 46 27 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Find the Sixth 
 Smallest Element lo hi k: 6 9 23 3 41 22 8 46 28 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 0123456 Example: Find the Fifth 
 Smallest Element lo hi 0123456 s k: 6 8 3 9 41 22 23 46 29 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Find the Fifth 
 Smallest Element lo hi 0123456 k: 3 8 3 9 41 22 23 46 30 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Find the Fifth 
 Smallest Element lo hi 8 3 9 41 22 23 46 31 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 0123456 si Example: Find the Fifth 
 Smallest Element lo hi 8 3 9 41 22 23 46 32 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 0123456 si Example: Find the Fifth 
 Smallest Element lo hi 8 3 9 41 22 23 46 33 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 0123456 si Example: Find the Fifth 
 Smallest Element lo hi 8 3 9 41 22 23 46 34 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 0123456 i s Example: Find the Fifth 
 Smallest Element lo hi 8 3 9 41 22 23 46 35 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 0123456 si Example: Find the Fifth 
 Smallest Element lo hi 8 3 9 41 22 23 46 36 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 0123456 s Example: Find the Fifth 
 Smallest Element lo hi 8 3 9 23 22 41 46 37 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 0123456 s Example: Find the Fifth 
 Smallest Element lo hi k: 3 8 3 9 23 22 41 46 38 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 0123456 s Example: Find the Fifth 
 Smallest Element lo hi k: 3 8 3 9 23 22 41 46 39 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License returns 41! 0123456 s 40 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License QuickSelect Complexity • Worst case complexity for QuickSelect is Average-case complexity is linear. • quadratic, 41 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Interpolation Search • Think about how you search for an entry in the telephone directory: If you look for ‘Zobel’, you make a rough estimate of where to do the first probe—very close to the end of the directory. This is the idea in interpolation search. • If the elements of a sorted array are distributed • reasonably evenly, we can do better than binary search! When searching for k in the array segment A[lo] to A[hi], • take into account where k is, relative to A[lo] and A[hi]. Interpolation Search A: 0123456 Suppose we are searching for k = 83 40 20 0 4 9 13 22 41 83 96 mid = A[lo] + ⌊ 120 100 k − A[lo] 80 A[hi] − 60 A[lo] ⋅(hi−lo)⌋ 42 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 01234567 Interpolation Search Instead of computing the mid-point m as in binary • search:
 
 
 m ← ⌊(lo + hi)/2⌋ we instead perform linear interpolation between the points (lo,A[lo]) and (hi,A[hi]). That is, we use:
 
 
 m←lo+⌊ k−A[lo] (hi−lo)⌋ A[hi] − A[lo] 43 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License • • Interpolation search has average complexity O(log log n) It is the right choice for large arrays when elements are uniformly distributed 44 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Next Week • • Learn to divide and conquer! Read Levitin Chapter 5, but skip 5.4.