The primary topics in this part of the specialization are: asymptotic ("Big-oh") notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).
O(n log n) Algorithm for Counting Inversions I
Loading...
From the course by Stanford University
Divide and Conquer, Sorting and Searching, and Randomized Algorithms
2513 ratings
From the lesson
Week 2
Divide-and-conquer basics; the master method for analyzing divide and conquer algorithms.
Meet the Instructors
Tim RoughgardenProfessor
Computer Science
In this next series of videos, we'll get some more practice applying the divide and
conquer algorithm and design paradigm to various problems. This will also give us a
glimpse of the kinds of application [inaudible] to which it's been
successfully applied. We're gonna start by extending the merge sort algorithm to
solve a problem involving counting the number of inversions of an array. Before
we tackle the specific problem of counting the number of inversions in an array, let
me say a few words about the divide and conquer paradigm in general. So again,
you've already seen the totally canonical example of divide and conquer, namely
merge sort. So the following three conceptual steps will be familiar to you.
The first step, no prizes for guessing is you divide. The problem. Into smaller
sub-problems. Sometimes this division happens only in your mind. It's really
more of a conceptual step than part of your code. Sometimes you really do copy
over parts of the input into say new arrays to pass on to your recursive calls.
The second step, again no prizes here, is you conquer the sub-problems just using
recursion. So for example, in Merge Sort, you conceptually divide the array into two
different pieces. And then you [inaudible] with the conquer or sort to the first half
of the array. And you, you do the same thing with the second half of the array.
Now, of course, it's not quite as easy as just doing these two steps. Dividing the
problem, and then solving the sub problems recursively. Usually, you have some extra
cleanup work after the recursive calls, and to stitch together the solutions to
the sub problems into one for the big problem, the problem that you actually
care about. Recall, for example, in Merge Sort, after our recursive calls, the left
half of the array was sorted, the right half of the array was sorted. But we still
had to stitch those together. Merge into a sorted version of the entire array. So the
[inaudible] step is to combine. The solutions to the subproblem into one
problem. Generally the largest amount of ingenuity happens in the third step. How
do you actually quickly combine solutions to subproblems into one to the original
problem? Sometimes you also get some cleverness in the first step with
division. Sometimes it's as simple as just spliting a ray in two. But there are cases
where the division step also has some ingenuity. Now let's move on to the
specific problem of counting inversions and see how to apply this divide and
conquer paradygm. So let begin by defining the problem formally now. We're given as
input an array A with a length N. And you can define the problem so that the array a
contains any ole distinct numbers. But, let's just keep thing simple and assume
that it contains the numbers one through n. The integers in that range in some
order. That captures the essence of the problem. And the goal is to compute the
number of inversions of this array so what's an inversion you may ask well an
inversion is just a pair of array [inaudible] I and J with I smaller than J
so that earlier array entry the I entry is bigger than the latter one the Jake one so
one thing that should be evident is that if the array contains these numbers in
sorted order if the array is simply one two three four all the way up to N then
the number of inversions is zero. The converse you might also want to think
through if the array has any other ordering of the numbers between one and N
other than the assorted one, then it's going to have a non. Of zero number of
inversions. Let's look at another example. So'spose we have an array of six entries.
So the numbers one thru six in the following order. One, three, five followed
by two, four, six. So how many inversions does this array have? So again what we
need to look for are pairs of array entries so that the earlier or left entry
is bigger than the later or right entry. So one example which we see right here
would five and two. Those are right next to each other and out of order, the
earlier entry is bigger than the other one. But there's others, there's three and
two for example Those are out of order. And, five and four are also out of order.
And I'll leave it to you to check that those are the only three pairs that are
out of order. So summarizing the inversions in this array of length six are
3-2, 5-2, and 5-4. Corresponding to the array entries, 2-4, 3-4, and 3-5.
Pictorially, we can think of it thusly, we can first. Write down the numbers in
order, one up to six. And then we can write down the numbers again but, ordered
in the way that their given in the input array. So, one three five two four six.
And then we can connect the dots, meaning we connect one to one. Reconnect two to
two, and so on. It turns out, and I'll leave to for you to, to think this
through, that the number of crossing pairs of line segments prescisely correspond to
the number of inversions. So we see that there are one, two, three crossing line
segments. And these are exactly in correspondence with the three inversions,
we found earlier. Five and two, three and two, and five and four. Now, [inaudible]
wanna solve this problem you might ask. Well there's few reasons that come up. One
would be to have a numerical similarity measure that quantifies how close to
[inaudible] lists are to each other. So for example, suppose I took you and a
friend, and I took, identified ten movies that both of you had seen. And I asked
each of you to order, or to rank these movies from your most favorite to your
least favorite. Now I can form an array, and compute inversions. And it quantifies,
in some sense, how dissimilar your two rankings are to each other. So in more
detail, in the first entry of this array, I would put down the ranking that your
friend gave to your favorite movie. So if you had your favorite movie, Star Wars or
whatever. And your friend only thought it was the fifth best out of the ten, then I
would write down a five in the first entry of this array. Generally, I would take
your second favorite movie. I would look at how your friend ranked that. I would
put that in the second entry of the array and so on, all the way up to the tenth
entry of the array, where I would put your friend's ranking of your least favorite
movie. Now, if you have exactly identical preferences, if you rank them exactly the
same way, the number of inversions of this array would be zero. And in general, the
more inversions this array has, it quantifies that your lists look more and
more different from each other. Now why might you want to do this why might you
want to know whether two different people ranked things in the similar way had
similar preferences well one reason might be what's called collaborative filtering,
probably many of you have had the experience of going to a website and if
you've made a few purchases through this website it starts recommending further
purchases for you, so one way to solve this problem under the hood, is to look at
your purchases look at what you seem to like, find other people who have similar
preferences similar history look at things they've bought that you haven't, and then
recommend. New products to you based on what similar customers seemed to have
bought. So this problem captures some of the essence of identifying which customers
or which people are similar based on data about what they prefer. So just to make
sure we're all on the same page, let me pause for a brief quiz. We've already
noticed that a given array will have zero inversions, if and only if it's in sorted
order. If it only contains the numbers of one through N in order. So, on the other
side, what is the largest number of inversions an array could possibly have?
Let's say, just for an array of size six, like the one in this example here. So the
answer to this question is the first one. Fifteen. Or in general in an N. Element
array the largest number of inversions is N. Choose two. Also known as N times N
minus one over two. Which, again, in the case of a [inaudible] is going to evaluate
to fifteen. The reason is, the worst case is when the array is in backwards order,
reverse [inaudible] order, and every single pair of [inaudible] indices is
inverted. And so the number of indices IJ, with I less than J is precisely
[inaudible] too. Let's now turn our attention to the problem of computing the
number of inversions of an array as quickly as possible. So one option that is
certainly available to us is the brute force algorithm. And by brute force I just
mean we could set up a double four loop. One which goes through I, one which goes
through J bigger than I, and we just check each pair IJ individually with I less than
J whether that particular pair of array entities AI and AJ is inverted and if it
is then we add it to our running count. And then we return the final count at the
end of the double four loop. That's certainly correct. The only problem is, as
we just observed, there's N [inaudible] two or a quadratic number of potential
inversions so this algorithm's almost going to run in time quadratic in the
array link. Now remember the mantra of any good algorithm designer. Can we do better?
And the answer is yes. And the method we'll be using, divide and conquer. The
way in which we'll divide will be motivated directly by merge sort where we
recurs e separately on the left and the right half's of the array. We're gonna do
the same thing here. To understand how much progress we can make purely using
recursion let's classify the inversions of array into one of three types. So suppose
we have an inversion of an array I, J, and remember in an inversion you always have I
less than J. We're gonna call it a left inversion. If both of the array indices
are at most N over two, where N is the array length. We're gonna call it a right
inversion if they're both strictly greater than N over two. And we're gonna call it a
split inversion if the smaller index is at most N over two and the larger index is
bigger than N over two. We can discuss the progress made by recursion in these terms.
When we recurse on the left-half of an array, if we implement our algorithm
correctly, we'll successfully be able to count all of the inversions located purely
in that first half. Those are precisely the left inversions. Similarly, a second
recursive call on just the right half of an array, the second half of an
[inaudible] array will successfully count all of the right inversions. There remains
the questions of how to count the split inversions. But we shouldn't be surprised
there's some residual work left over, even after the recursive calls do their job.
That, of course, was the case at Merge Short, where [inaudible] magically took
care of sorting the left half of the array, sorting the right half of the
array. But there was still, after their return, the matter of merging those two
sorted lists into one. And here again, after the recursion is gonna be the matter
of cleaning up and counting the number of split inversions. So for example if you go
back to the six element array we worked through before, 135246, you'll notice that
there, in fact, all of the inversions are split. So the recursive calls will both
come back counting zero inversions. And all of the work for that example will be
done by the count split inversions subroutine. So let's summarize where
things stand given underspecified high level description of the algorithm as we
envision it. There is a base case. I'll go ahead and write it down for completeness,
which is if we're given a one element array, then there's certainly no inversion
so we can just immediately return the answer zero. For any bigger array, we're
going to divde and conquer. So we'll count the left inversions with a recursive call.
The right inversions with a recursive call. And then we'll have some currently
unimplemented subroutine that counts the split inversions. Since every inversion is
either left or right, or split, and can't be any more than one of those three, then,
having done these three things, we can simply return their sum. So that's our
high level attack on how we're gonna count up the number of inversions. And of
course, we need to specify how we're gonna count the number of split inversions. And
moreover, we lack that subroutine to run quickly. An analogy to emerge short,
where, outside the recursive calls, we did merely linear work. Outs-, in the merge
subroutine. Here, we'd like to do only linear work in counting up the number of
split inversions. If we succeed in this goal, if we produce a correct and linear
time of limitation to count up the number of split incursions, then this entire
recursive algorithm will run in big O. Of N. Log in time. The reason the overall out
rhythm will run in O. Of N. Log in time is exactly the same reason that merge short
ran in N. Log in time. There's two recursive calls. Each on a problem of
one-half the size. And outside of the recursive calls we would be doing linear
work. So you could copy down exactly the same recursion tree argument we used for
merge short. It would apply equally well here. Alternatively, very soon we will
cover the master method, and as one very special case it will prove that this
algorithm, if we can implement it thusly, will run in O. Of N. Log in time. Now one
thing to realize, is this is a fairly ambitious goal, to count up the number of
split inversions in linear time. It's not that there can't be too many split
inversions. There can actually be a lot of them. If you have an array where the first
half of the array contains the numbers N over two plus one, up to N. Whereas the
second part of the array contains the numbers one up to N over two, that has a
quadratic number of inversions, all of which are split. So, what we're attempting
to do here is count up a quadratic number of things using only linear time. Can it
really be done? Yes is can, as we'll see in the next video.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
