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.