I haven't said how I'm going to get those sorted lists, but imagine I had two sorted lists like that. Just to give you an example, here's one list, 3121724 Here's another list, 12430. Suppose I want to merge two lists, and they're sorted. How much work do I have to do to actually merge them together? So let me give you an example. Let's assume that I could somehow get to the stage where I've got two sorted lists. And here's the idea behind merge sort, actually I'm going to back into it in a funny way. Von Neumann one of the pioneers of computer science. And it's actually a fairly old algorithm. And that particular algorithm is actually a really nice algorithm called merge sort. I want to sort it into a obviously a sorted list. I've got an unordered list of n elements. I'm going to use exactly that same ideas to tackle sort. But there's the idea of divide and conquer. The combination was also sort of trivial in this case because the solution to the sub-problem was, in fact, the solution to the larger problem. We actually threw half of the list away and we kept dividing it down, until ultimately we got something What was the divide? The divide was breaking a big search up into half a search. Now, in theīinary search case, in some sense, this is a little bit trivial. It's going to be easier to conquer if you like, and then I'm going to merge them back. I'm going to divide it up into sub-problems with the hope that those sub-problems get easier. For each of those sub-problems we're going to solve them independently, and then we're going to combine those solutions.Īnd it's called divide and conquer for the obvious reason. I'll come back in a second to help binary searches matches in that, but that's what Divide and conquer says basically do the following: split the problem into several sub-problems of the same type. Let's say what this actually means, divide and conquer. Me say - boy, I could have made a really bad political joke there, which I will forego, right. Sort of an Attila the Hun kind of approach to doing things if you like. At the end of the lecture I said binary search was an example of a divide and conquer algorithm. To set the stage for this, let's go back just for a second to binary search. One of the two things I want to do today. Offs, but I still haven't said how I'm going to get an n log n sorting algorithm, and that's what I want to do today. It depends on n and k but obviously as n gets big, that one is going to be better.Īnd that's just a way of reminding you that we want to think carefully, but what are the things we're trying to measure when we talk about complexity here? It's both the size of the thing and how often are we going to use it? And there are some trade In general going to be much better than k times n. And we suggested well this is better than that. Whereas in the ordered case, I need to get them sorted, which is still n log n, but then the search is only log n. So if I have to do k searches, then in the linear case, I got to do order n things k times. To just search once in a list, I'm going to search multiple times. And this led to this idea of amortization, which is I need to not only factor in the cost, but how am I going to use it? And typically, I'm not going Once I have it sorted I can search it in log n time, but that's still isn't as good as just doing n. Was going to take n log n time, assuming I can do that. But in that case, we said well to sort it I could still do the linear case, which is order n or I could say, look, take the list, let's sort it and then search it. But it changed in a way that I want to remind you.Īnd the change was, that in this case, if I'm doing a single search, I've got a choice. Order it, and in particular, if we could order it in n log n time, and we still haven't done that, but if we could do that, then we said the complexity changed a little bit. And then one of the things that I suggested was that if we could figure out some way to Got to walk through the whole list to see if the thing is there. If it was an unordered list, we were basically stuck with linear search. And we said that was log rhythmic, took log n time where n is the size of the list. We said if we had an ordered list, we could use binary search. And I'll remind you that we sort of a separated out two cases. I want to remind you, we were talking about search, which is a very fundamental thing that we do in a whole lot of applications. PROFESSOR: Last time we were talking about binary search and I sort of left a promise to you which I need to pick up.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |