Материал готовится,

пожалуйста, возвращайтесь позднее

пожалуйста, возвращайтесь позднее

Today we're going to not talk about sorting. This is an exciting new development. We're going to talk about another problem, a related problem, but a different problem. We're going to talk about another problem that we would like to solve in linear time. Last class we talked about we could do sorting in linear time. To do that we needed some additional assumptions. Today we're going to look at a problem that really only needs linear time, even though at first glance it might look like it requires sorting. So this is going to be an easier problem. The problem is I give you a bunch of numbers.

Let's call them elements. And they are in some array, let's say. And they're in no particular order, so unsorted. I want to find the kth smallest element. This is called the element of rank k. In other words, I have this list of numbers which is unsorted. And, if I were to sort it, I would like to know what the kth element is. But I'm not allowed to sort it. One solution to this problem, this is the naïve algorithm, is you just sort and then return the kth element. This is another possible definition of the problem.

And we would like to do better than that. So you could sort, what's called the array A, and then return A[k]. That is one thing we could do. And if we use heap sort or mergesort, this will take n lg n time. We would like to do better than n lg n. Ideally linear time. The problem is pretty natural, straightforward. It has various applications. Depending on how you choose k, k could be any number between 1 and n. For example, if we choose k=1 that element has a name. Any suggestions of what the name is? The minimum. That's easy. Any suggestions on how we could find the minimum element in an array in linear time? Right.

Just scan through the array. Keep track of what the smallest number is that you've seen. The same thing with the maximum, k=n. These are rather trivial. But a more interesting version of the order statistic problem is to find the median. This is either k equals n plus 1 over 2 floor or ceiling. I will call both of those elements medians. Finding the median of an unsorted array in linear time is quite tricky. And that sort of is the main goal of this lecture, is to be able to find the medians. For free we're going to be able to find the arbitrary kth smallest element, but typically we're most interested in finding the median. And on Friday in recitation you'll see why that is so useful. There are all sorts of situations where you can use median for really effective divide-and-conquer without having to sort.

You can solve a lot of problems in linear time as a result. And we're going to cover today two algorithms for finding order statistics. Both of them are linear time. The first one is randomized, so it's only linear expected time. And the second one is worst-case linear time, and it will build on the randomized version. Let's start with a randomize divide-and-conquer algorithm. This algorithm is called rand-select.

And the parameters are a little bit more than what we're used to. The order statistics problem you're given an array A. And here I've changed notation and I'm looking for the ith smallest element, so i is the index I'm looking for. And I'm also going to change the problem a little bit. And instead of trying to find it in the whole array, I'm going to look in a particular interval of the array, A from p up to q.

We're going to need that for a recursion. This better be a recursive algorithm because we're using divide-and-conquer.

Let's call them elements. And they are in some array, let's say. And they're in no particular order, so unsorted. I want to find the kth smallest element. This is called the element of rank k. In other words, I have this list of numbers which is unsorted. And, if I were to sort it, I would like to know what the kth element is. But I'm not allowed to sort it. One solution to this problem, this is the naïve algorithm, is you just sort and then return the kth element. This is another possible definition of the problem.

And we would like to do better than that. So you could sort, what's called the array A, and then return A[k]. That is one thing we could do. And if we use heap sort or mergesort, this will take n lg n time. We would like to do better than n lg n. Ideally linear time. The problem is pretty natural, straightforward. It has various applications. Depending on how you choose k, k could be any number between 1 and n. For example, if we choose k=1 that element has a name. Any suggestions of what the name is? The minimum. That's easy. Any suggestions on how we could find the minimum element in an array in linear time? Right.

Just scan through the array. Keep track of what the smallest number is that you've seen. The same thing with the maximum, k=n. These are rather trivial. But a more interesting version of the order statistic problem is to find the median. This is either k equals n plus 1 over 2 floor or ceiling. I will call both of those elements medians. Finding the median of an unsorted array in linear time is quite tricky. And that sort of is the main goal of this lecture, is to be able to find the medians. For free we're going to be able to find the arbitrary kth smallest element, but typically we're most interested in finding the median. And on Friday in recitation you'll see why that is so useful. There are all sorts of situations where you can use median for really effective divide-and-conquer without having to sort.

You can solve a lot of problems in linear time as a result. And we're going to cover today two algorithms for finding order statistics. Both of them are linear time. The first one is randomized, so it's only linear expected time. And the second one is worst-case linear time, and it will build on the randomized version. Let's start with a randomize divide-and-conquer algorithm. This algorithm is called rand-select.

And the parameters are a little bit more than what we're used to. The order statistics problem you're given an array A. And here I've changed notation and I'm looking for the ith smallest element, so i is the index I'm looking for. And I'm also going to change the problem a little bit. And instead of trying to find it in the whole array, I'm going to look in a particular interval of the array, A from p up to q.

We're going to need that for a recursion. This better be a recursive algorithm because we're using divide-and-conquer.

Загрузка...

Выбрать следующее задание

Ты добавил

Выбрать следующее задание

Ты добавил