CS代考 COMP90038 – cscodehelp代写

COMP90038
Algorithms and Complexity
Lecture 10: Decrease-and-Conquer-by-a-Factor (with thanks to Harald Søndergaard)

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: n ⋅ m = n2 ⋅ 2 m For odd n: n − 1 • • nm 40 184 10 736 • 81 92 92 20 368 n⋅m= 2 ⋅2m+m Thus, ~halve n repeatedly, until 5 1 1472 1472 5888 5888 = 7452 2 2944 • n = 1. Add up all odd values of m 12 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 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 13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 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)). 3 8 9 22 23 41 46 • A: 0123456 However, sorting the array seems like overkill. 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 Sixth 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 Sixth 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 Sixth 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 Sixth 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 Sixth 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 Sixth 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 Sixth 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 Sixth 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 Sixth 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 Sixth 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 Sixth 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 mid=lo+⌊ k−A A[hi] − 4 9 13 22 41 83 96 120 100 [lo] 80 A[lo] 60 lo)⌋ 40 20 0 ⋅(hi− 01234567 42 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 43 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Interpolation Search Instead of computing the mid-point m as in binary 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] • search: • • 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.