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).
Deterministic Selection - Algorithm [Advanced - Optional]
Loading...
来自 Stanford University 的课程
Divide and Conquer, Sorting and Searching, and Randomized Algorithms
1645 个评分
从本节课中
Week 4
Linear-time selection; graphs, cuts, and the contraction algorithm.
与讲师见面
Tim RoughgardenProfessor
Computer Science
Previous videos covered an outstanding algorithm for the selection problem, the
problem of computing the Ith statistic of a given array. That algorithm which we
called the R select algorithm was excellent in two senses. First its super
practical, runs blazingly fast in practice. But also it enjoys a satisfying
theoretical guarantee. For every input array of length N at the expected running
time of R select is big O of N, where the expectation is over the random choices of
the pivots that R select makes during execution, now in this optional video
I'm going to teach you yet another algorithm for the selection
problem. Well why bother given that our select is so good? Well frankly, I just
can't help myself. The ideas of this algorithm are just too cool not to tell
you about, at least in optional video like this one. The selection algorithm
, we cover here is deterministic. That is, it uses no randomization
whatsoever. And it's still gonna run in linear time, big O of N time. But now, in
the worst case for every single input array. Thus, the same way Merge Short gets
the same asymptotic running time, big O of N log N, as quick sorts gets on
average. This deterministic algorithm will get the same running time O of N, as the R
select algorithm does on average. That said, the algorithm we're gonna cover
here, well, it's not slow. It's not as fast as R select in practice, both because
the hidden constants in it are larger. And also because it doesn't' operate in place.
For those of you who are feeling keen, you might wanna try coding up both the
randomized and the deterministic selection algorithms, and make your own measurements
about how much better the randomized one seems to be. But if you have an
appreciation for Boolean algorithms, I think you'll enjoy these lectures
nonetheless. So let me remind of the problem. This is the i-th order
statistic problem. So we're given an array, it has N distinct entries. Again,
the distinctness is for simplicity. And you're given a number I between one and N.
You're responsible for finding the i-th smallest number, which we call
the i-th order statistic. For example, if I is something like N over
two, then we're looking for the median. So let's briefly review the randomized
selection algorithm. We can think of the deterministic algorithm covered here as a
modification of the randomized algorithm, the R select algorithm. So when that
algorithm is passed in array with length N, and when you're looking for the
i-th order statistic, as usual, there's a trivial base case. But when
you're not in the base case, just like in Quick Sort, what you do is you're gonna
partition the array around pivot element P. Now, how are you gonna choose P? Well,
just like Quick Sort, in the randomized algorithm, you choose it uniformly at
random. So each of the N elements of the input array are equally likely to be
chosen. As the pivot. So, call that pivot p. Now, do the partitioning. Remember
partitioning puts all of the elements less than the pivot to the left of the pivot.
We call that the first part of the partitioned array. Anything big, bigger
than the pivot gets moved to the right of the pivot. We call that the second part of
the array. And let j denote the position of the pivot in this partitioned array.
Equivalently, let j be what order statistic that the pivot winds up
happening to be. Right? So, we happen to choose the minimum element then J's gonna
be equal to one. If we happen to choose the maximum element, J's gonna be equal to
n. And so on. So, there's always the lucky case, chance one in N, that we happen to
choose the Ith order statistic as our pivot. So, we're going to find that out
when we notice that J equals I. In that super lucky case, we just return the pivot
and we're done. That's what we're looking for in the first place. Of course, that's
so rare it's not worth worrying about, so really the two main cases depend on
whether the pivot that we randomly choose is bigger than what we are looking for or
if it's less than what we are looking for. So, if it's bigger than what we are
looking for, that means J is bigger than I, we're looking for the Ith smallest, we
randomly chose the J'th smallest. Then remember we know that the Ith smallest
element has to lie to the left of the pivot. Good element in that first part of
the partition array. So we recurs there. It's an array that has J-1 elements in it,
everything less than the pivot. And we're still looking for the Ith smallest among
them. In the other case, this was the case covered in a quiz a couple videos back, if
we guess a pivot element that is less than what we're looking for, well then we
should discard everything less than the pivot and the pivot itself. So we should
recurs on the second part of A, stuff bigger than the pivot. We know that's
where what we're looking for lies. And having thrown away J elements, the
smallest ones at that. We're rehearsing on a ray of [inaudible] and minus J, I'm
looking for the [inaudible] smallest element in that second part. So, that was
the randomized selection algorithm, and you'll recall the intuition for why this
works is random pivot should usually give pretty good splits. So the way the
analysis went is we should. Each iteration, each recursive call, with 50
percent probability, we get a 25/75 split or better. Therefore, on average, every
two recursive calls, we are pretty aggressively shrinking the size of the
recursive call. And for that reason, we should get, something like a linear time
bound. We do almost as well as if we picked the median in every single call,
just because random pivots are a good enough proxy of best case pivots, of. The
median. So now the big question is: suppose we weren't permitted to make use
of randomizations. Suppose this choose-a-random-pivot trick was not in our
tool box. What could we do? How are we going to deterministically choose a good
pivot? Let's just remember quickly what it means to be a good pivot. A good pivot is
one that gives us a balanced split, after we do the partitioning of the array. That
is, we want as close to a 50/50 split between the first and the second parts of
the partitioned array as possible. Now, what pivot would give us the perfect 50/50
split? Well, in fact, that would be the median. Well, that seems like a totally
ridiculous observation, because we canonically, are trying to find the
median. So previously we were able to be lazy, and we just picked a random pivot,
and used that as a pretty good proxy for the best case pivot. But now, we have to
have some subroutine that deterministically finds us a pretty good
approximation of the median. And the big idea in this linear time selection
algorithm, is to use what's called the median of medians as a proxy for the true
meaning of the input array. So when I say median of medians, you're not supposed to
know what I'm talking about. You're just supposed to be intrigued. Now, let me
explain a little bit further. Here's the plan, we're gonna have our new
implementation of chose pivot and it's gonna be deterministic. You will see no
randomization on this slide, I promise. So the high-level strategy is gonna be we're
gonna think about the elements of this array like sports teams, and we're gonna
run a tournament, a 2-round. Knockout tournament, and the winner of this
tournament is going to be who we return as the proposed pivot element. Then we'll
have to prove that this is a pretty good pivot element. So there's gonna be two
rounds in this tournament. Each element, each team is gonna first participate in a
world group, if you will. So they'll be, small groups of five teams each, five
elements each. And to win your first round, you have to be the middle element
out of those five. So that'll give us N over five first round winners. And then
the winner of that second round is going to the med-, be the median of those N over
five winners from the first round. Here are the details. The first step isn't
really something you actually do in the program, it's just conceptually. So
logically, we're going to take this array capital A, which has N elements, and we're
gonna think of it as comprising N over five groups with five elements each. So if
N is not a multiple of five, obviously, there'll be one extra group that has size
between one and four. Now for each of these groups of five, we're going to
compute the median, so the middle element of those five. Now for five elements, we
may as well just invoke a reduction to sorting; we're just gonna sort each group
separately, and then use the middle element, which is the median. It doesn't
really how you do the sorting. Because after all, there's only five elements. But
you know, let's use [inaudible] sort, what the heck. Now what we're going to do is
we're going to take our first round winners and we're gonna copy them over
into their own private array. Now this next step is the one that's going to seem
dangerously like cheating, dangerously like I'm doing something circular and not
actually defining a proper algorithm, so c you'll notice has linked over n over five.
We started with an array of link n. This is a smaller input. So let's recursively
compute the median of this array capital c. That is the second round of our
tournament amongst the n over five first-round winners, the n over five
middle elements of the sorted groups. We recursively compute the median, that's our
final winner, and that's what we return as the pivot element from this subroutine.
Now I realize it's very hard to keep track of both what's happening internal to this
juice pivot subroutine and what's happening in the calling function of our
deterministic selection algorithm. So let me put them both together and show them to
you, cleaned up, on a single slide. So, here is the proposed deterministic,
selection algorithm. So, this algorithm uses no randomization. Previously, the
only randomization was in choosing the pivot. Now we have a deterministic
subroutine for choosing the pivot, and so there's no randomization at all. I've
taken the liberty of in-lining true's pivot subroutine. So that is exactly what
lines one, two, and three are. I haven't written down the base case just to save
space I'm sure you can remember it, so if you're not in the base case. What did we
do before? The first thing we do is choose a random pivot. What do we do now? Well,
we have steps one through three. We do something much more clever to choose a
pivot. And this is exactly what we said on the last slide. We break the array into
groups of five. We sort each group, for example, using merge sort. We copy over
the middle element of each of the n over five groups into their own array capital
c. And, then, we recursively compute the median of c. So, when we recurs on select
that we pass the input c. C has n over five elements so that's the new link.
That's a smaller link than what we start with so it's a legitimate recursive call
refining the median of n over five element. So, that's gonna be the n over
tenth order statistic. As usual. Well to keep things clear I'm ignoring stuff like
fractions, in your real implementation you'd just round it up or down. As
appropriate. So steps one through three are the new [inaudible] step routine that
replaces the randomized selection that we had before. Steps four through seven are
exactly the same as before. We've changed nothing. All we have done is ripped out
that one line where we chose the pivot randomly and pasted in these lines one
through three. That is the only change to the randomized selection algorithm. So,
the next quiz is a standard check that you understand this algorithm, at least, not
necessarily why it?s fast; but, at least, just how it actually works. And I only ask
you to identify how many recursive calls there are, each time. So, for example in
[inaudible] there's two recursive calls, in quick-sort there's two recursive calls,
in r-select there's one recursive call. How many recursive calls do you have each
time, outside of the base case in the d-select algorithm? All right, so the
correct answer is two. There are two recursive calls in deselect, and maybe the
easiest way to answer this question is not to think too hard about it and literally
just inspect the code and count, right namely there's one recursive call in line
three, and there's one recursive call in either six or seven, so quite literally,
you know there's seven lines of code, and two of the ones that get executed have a
recursive call so the answer is two. Now what's confusing is that in the random, a
couple things, first in the randomized selection algorithm, we only have one
recursive call. We have the recursive call. In line six or seven, we didn't have
this in line three. That one in line three is new compared to the randomized
procedure. So we're kind of used to thinking of one recursive call using the
divide and conquer approach to selection, here we have two. Moreover. Conceptually.
The roll of these two recursive calls are different. So the one in line six or seven
is the one we're used to. That's after you've done the partitioning so you have a
smaller sub-problem and then you just recursively find the residual or statistic
in the residual array. That's sort of the standard divide and conquer approach.
What's sort all crazy. Is this second use of a recursive call which is part of
identifying a good pivot element for this outer recursive call and this is so
counter-intuitive, many students in my experience don't even think that this
algorithm will hold, sort of, they sort of expect it to go into an infinite loop. But
again, that sort of over thinking it. So let's just compare this to an algorithm
like merge sort. What does merge sort do? Well it does two recursive calls and it
does some other stuff. Okay. It does linear work. That's what it does to merge.
And then there are two recursive calls on smaller sub problems, right? No issue. We
definitely feel confident that merge [inaudible] is gonna terminate because the
sub problems keep getting smaller. What does deselect do, if you squint? So don't
think about the details just [inaudible] high level. What is the work done in
deselect? Well. There are two recursive calls, there's [inaudible] one's in line
three, one's in line six or seven, but there's two recursive calls on sm, smaller
sub problem sizes. And there's some other stuff. There's some stuff in steps one and
two and four, but whatever. Those are recursive calls. It does some work. Two
recurs have caused the smaller sub-problems, TI's got to terminate. We
don't know what the run time is, but it's got to terminate, okay? So if you're
worried about this terminating, forget about the fact that the two recurs of
cause have different semantics and just remember, if ever, you only recurs on
smaller sub-problems, you're definitely going to terminate. Now, of course who
knows what the running time is? I owe you an argument on why it would be anything
reasonable, that's going to come later. In fact what I'm gonna prove to you is not
only does this selection algorithm terminate, run in finite time, it actually
runs in linear time. No matter what the input array is. So where as with R select,
we could only discuss its expected running time being linear. We showed that with
disastrously bad choices for pivots, R selects can actually take quadratic time.
Under no circumstances will deselect ever take, ever take quadratic time. So for
every input array it's big O of N time. There's no randomization because we don't
randomly do anything in choose pivot, so there's no need to talk about average
running time; just the worst case running time over all inputs is O of N. That said,
I want to reiterate the warning I gave you at the very beginning of this video which
is, if you actually need to implement a selection algorithm, you know, this one
wouldn't be a disaster. But it is not the method of choice, so I don't want you to
be misled. As I said there are two reasons for this. The first is that the constants
hidden in the begon notation are larger for V select than for R select. That will
be somewhat evident from the analyses that we give for the two algorithms. The second
reason is, recall we made a big deal about how partitioning works in place and
therefore quicksort and r select also work in place, that is, with no real additional
memory storage. But in this deselect algorithm we do need this extra array c to
copy over the middle elements, the first round winners. And so the extra memory, as
usual, slows down the practical performance. One final comment. So for
many of the algorithms that we cover, I hope I explain them clearly enough that
their elegance shines through and that for many of them you feel like you could have
up with it yourself, if only you'd been in the right place at the right time. I think
that's a great way to feel and a great way to appreciate some of these very cool
algorithms. That said, linear time selection, I don't blame you if it, if you
feel like you never might have come up with this algorithm. I think that's a
totally reasonable way to feel after you see this code. If it makes you feel
better, let me tell you about who came up with this algorithm. It's quite old at
this point, about 40 years, from 1973. And the authors, there are five of them and at
the time this was very unusual. So, Manuel Blum. Bob Floyd. Vaughn Pratt. Ron Rivest.
And Bob Targen. And this is a pretty heavy weight line up, so as we've discussed in
the past, the highest award in computer science is the ACM Turing award given once
each year. And I like to ask my algorithms classes how many of these authors do they
think, have been awarded a Turing award. I've asked him many times. The favorite
answer anyone's ever given me has been. Six, which I think is in spirit should be
correct. Strictly speaking the answer is four. So, the only one of these five
authors that doesn't have a Touring award is Von Pratt, although he's done
remarkable things spanning the gambit from co-founding Sun Systems to having very
famous theorems about, for example, testing primality. But the other four have
all been awarded the Touring award at some point. So in chronological order, so the
late Bob Floyd who was a professor here at Stanford. Was awarded the 1978 [inaudible]
award, both for contributions to algorithms but also to program languages
and compilers. So Bob Targen who, as we speak, is here as a visitor at Stanford
and has spent his Ph. D here and has been here as a faculty at times, was awarded it
for contributions to graph algorithms and data structures. We'll talk some more
about some of his other contributions in future courses. Manuel Blum was awarded
the Turing award in'95 largely for contributions in cryptography, and many of
you probably know Ron Rivest as the R in the RSA cryptosystem. So he, won the,
Turing award along with Shamir and Adleman back in'02. So in summary, if this
algorithm seems like one that might have alluded you even on your most creative
days, I wouldn't feel bad about it. This is a, this is a quite clever algorithm. So
let's now turn to the analysis and explain why it runs in linear time in the worst
