程序代写代做代考 algorithm 10.key

10.key

http://people.eng.unimelb.edu.au/tobym

@tobycmurray

toby.murray@unimelb.edu.au

DMD 8.17 (Level 8, Doug McDonell Bldg)

Toby Murray

COMP90038  
Algorithms and Complexity

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

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).

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
binary search.

• Decrease-by-a-variable-factor is exemplified by
interpolation search.

• Let us look at these and other instances.

Binary Search
• This is a well-known approach for searching for an element k

in a sorted array.

• Start by comparing against the array’s middle element A[m].
If A[m] = k we are done.

• 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. 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 6 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 lo: 0 hi: 6 k: 41 m: 3 BinSearch(A,7,41) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array 7 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,7,41) lo: 4 hi: 6 k: 41 m: 3 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array 8 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,7,41) lo: 4 hi: 6 k: 41 m: 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array 9 lo: 4 hi: 4 k: 41 m: 5 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,7,41) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array 10 lo: 4 hi: 4 k: 41 m: 4 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 BinSearch(A,7,41) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 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:    • A closed form is: • In the worst case, searching for k in an array of size 1,000,000 requires 20 comparisons. • The average-case time complexity is also Θ(log n) 11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Russian Peasant   Multiplication • A way of doing multiplication. • For even n:    • For odd n:    • Thus, ~halve n repeatedly, until   n = 1. Add up all odd values of m 12 n ⋅ m = n 2 ⋅ 2m n ⋅ m = n − 1 2 ⋅ 2m + m n m 81 92 92 40 184 20 368 10 736 5 1472 1472 2 2944 1 5888 5888 = 7452 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. • More generally, we would like to solve the problem of finding the kth smallest element. (e.g. when k=3) • 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)).    • However, sorting the array seems like overkill. 13 9 23 3 41 22 8 46A: 0 1 2 3 4 5 6 9 23 3 41 22 8 46A: 0 1 2 3 4 5 6 3 8 9 22 23 41 46A: 0 1 2 3 4 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 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. 14 9 23 3 41 22 8 46A: 0 1 2 3 4 5 6 3 8 9 23 22 41 46A: 0 1 2 3 4 5 6 Partitioning around the pivot 9 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Lomuto Partitioning 15 23 3 41 22 8 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Lomuto Partitioning 16 23 3 41 22 8 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Lomuto Partitioning 17 23 3 41 22 8 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Lomuto Partitioning 18 3 23 41 22 8 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Lomuto Partitioning 19 3 23 41 22 8 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Lomuto Partitioning 20 3 23 41 22 8 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Lomuto Partitioning 21 3 23 41 22 8 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Lomuto Partitioning 22 3 23 41 22 8 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Lomuto Partitioning 23 3 8 41 22 23 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Lomuto Partitioning 24 3 8 41 22 23 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Lomuto Partitioning 25 3 8 41 22 23 46 0 1 2 3 4 5 6 lo hi s Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 8 Lomuto Partitioning 26 3 9 41 22 23 46 0 1 2 3 4 5 6 lo hi s Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Finding the kth-smallest Element 27 8 3 9 41 22 23 46 0 1 2 3 4 5 6 lo hi s Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Find the Sixth   Smallest Element 28 9 23 3 41 22 8 46 0 1 2 3 4 5 6 lo hi k: 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Find the Fifth   Smallest Element 29 8 3 9 41 22 23 46 0 1 2 3 4 5 6 lo hi s k: 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Example: Find the Fifth   Smallest Element 30 8 3 41 22 23 46 0 1 2 3 4 5 6 lo hi k: 3 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Example: Find the Fifth   Smallest Element 31 8 3 41 22 23 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Example: Find the Fifth   Smallest Element 32 8 3 41 22 23 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Example: Find the Fifth   Smallest Element 33 8 3 41 22 23 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Example: Find the Fifth   Smallest Element 34 8 3 41 22 23 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Example: Find the Fifth   Smallest Element 35 8 3 41 22 23 46 0 1 2 3 4 5 6 lo hi s i Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9 Example: Find the Fifth   Smallest Element 36 8 3 41 22 23 46 0 1 2 3 4 5 6 lo hi s Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 239 Example: Find the Fifth   Smallest Element 37 8 3 22 41 46 0 1 2 3 4 5 6 lo hi s Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 239 Example: Find the Fifth   Smallest Element 38 8 3 22 41 46 0 1 2 3 4 5 6 lo hi s k: 3 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 239 Example: Find the Fifth   Smallest Element 39 8 3 22 41 46 0 1 2 3 4 5 6 lo hi s k: 3 returns 41! Copyright University of Melbourne 2016, provided under Creative Commons Attribution License QuickSelect Complexity • Worst case complexity for QuickSelect is quadratic, • Average-case complexity is linear. 40 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Interpolation Search • If the elements of a sorted array are distributed reasonably evenly, we can do better than binary 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. • 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]. 41 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 0 20 40 60 80 100 120 0 1 2 3 4 5 6 7 mid = A[lo] + ⌊ k − A[lo]A[hi] − A[lo] ⋅ (hi − lo)⌋ Interpolation Search 42 4 9 13 22 41 83 96A: 0 1 2 3 4 5 6 Suppose we are searching for k = 83 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Interpolation Search • Instead of computing the mid-point m as in binary search:      we instead perform linear interpolation between the points (lo,A[lo]) and (hi,A[hi]). That is, we use:      • Interpolation search has average complexity O(log log n) • It is the right choice for large arrays when elements are uniformly distributed 43 m ← ⌊(lo + hi)/2⌋ m ← lo + ⌊ k − A[lo]A[hi] − A[lo] (hi − lo)⌋ 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. 44

Related Posts