If you want to say that f is bounded below by g, that it grows no slower than g, you say that f(n) is Omega of g(n).
如果你想说f低于g，它的增长速度不低于g，你说f（n）是g（n）的Omega。
And that says that for some constant c, f(n) is at least c times g(n), for all large n.
并且这表示对于某些常数c，对于所有大的n，f（n）至少是g乘以g（n）。
Now instead of saying bounded above or bounded below, sometimes that you actually want to say that they grow at the same rate.
现在不是说上面或下面有界，有时你真的想说它们以相同的速度增长。
And for that you'd see f is Big-Theta of g(n).
为此，你会看到f是g（n）的Big-Theta。
Which means, that F is both Big-O of g, and, Big-Omega of G.
这意味着，F既是G的Big-O，又是G的Big-Omega。
Which says, up to constants, that f and g grow at the same rate.
根据常数，f和g以相同的速率增长。
Finally, sometimes instead of saying that f grows no faster than g, you actually have to say that it grows strictly slower than g, and for that you say f(n) is Little-o of g(n).
最后，有时不是说f的增长速度不比g快，你实际上不得不说它的生长速度比g慢，为此你说f（n）是g（n）的Little-o。
And that says that, not only is the ratio between f(n) and g(n) bounded above by some constant, but actually this constant can be made as small as you like.
这就是说，f（n）和g（n）之间的比率不仅高于某个常数，而且实际上这个常数可以根据你的喜好制作。
In particular this means that the ratio f(n) over g(n) goes to zero as n goes to infinity.
特别地，这意味着当n变为无穷大时，比率f（n）相对于g（n）变为零。
So, these are some other notations that you'll see now and then.
所以，这些是你偶尔会看到的其他一些符号。
You should keep them in mind.
你应该记住它们。
They're useful.
它们很有用。
Big-O is the one that usually shows up, because we actually want to bound our runtimes above.
Big-O通常会出现，因为我们实际上想要将运行时限制在上面。
It's sort of the big, important thing, but these guys are also useful.
这有点重要，但这些人也很有用。
So, to summarize the stuff on asymptotic notation.
所以，总结一下渐近符号的东西。
What it lets us do is ignore these messy details in the runtime analysis that we saw before.
它让我们做的是忽略我们之前看到的运行时分析中的这些混乱细节。
It produces very clean answers that tell us a lot about the asymptotic runtime of things.
它产生非常干净的答案，告诉我们很多关于事物的渐近运行时间。
And these together make it very useful.
这些一起使它非常有用。
It means we're going to be using it extensively throughout the course.
这意味着我们将在整个课程中广泛使用它。
So you really ought to get used to it.
所以你真的应该习惯它。
But, it does throw away a lot of practical useful information.
但是，它确实丢掉了许多实用的有用信息。
So if you really want to make your program fast, you need to look at more than just the Big-O runtime.
因此，如果您真的想让程序更快，那么您需要查看的不仅仅是Big-O运行时。
But, beyond that, we're going to use it.
但是，除此之外，我们将使用它。
With this lecture, we basically finished the sort of introductory material that we need.
通过本次讲座，我们基本上完成了所需的介绍性材料。
Next lecture I'll talk to you a little bit about sort of an overview of the rest of the course and some our philosophy for it.
下一讲我将与您讨论一下课程其余部分的概述以及我们的理念。
But after that, we'll really get into the meat of the subject.
但在那之后，我们将真正深入了解这一主题。
We'll start talking about key important ways to design algorithms.
我们将开始讨论设计算法的关键重要方法。
So, I hope you enjoy it.
所以，我希望你喜欢它。
------------- 18 -------------
01课程概述
Hello everybody, welcome back to the Data Structures and Algorithm specialization and the Algorithmic Toolbox course within it.
各位大家好，欢迎回到数据结构和算法专业化以及其中的算法工具箱课程。
This is the last lecture in the introductory unit and here we're going to give sort of an overview of the course.
这是介绍单元的最后一个讲座，在这里我们将对课程进行概述。
And in particular, what we're going to do is we're going to talk about sort of the philosophy of the course, and how it fits into the what we're going to be teaching you within the rest of this course.
特别是，我们要做的是，我们将谈论课程的哲学，以及它如何适应我们将在本课程的其余部分教授你的内容。
So, there's a problem.
所以，有一个问题。
Algorithm design is hard, and in particular it's hard to teach.
算法设计很难，尤其难以教授。
And by this I actually mean something pretty specific.
通过这个，我实际上意味着非常具体的东西。
Now, algorithms solve many, many different problems.
现在，算法解决了许多不同的问题。
You can use them to find paths between locations on a map, or find good matchings with some property, or identify images in a photograph.
您可以使用它们在地图上查找位置之间的路径，或找到与某些属性的良好匹配，或识别照片中的图像。
Many, many different sort of unrelated sounding problems can all be solved by algorithms.
许多不同类型的无关声音问题都可以通过算法解决。
And because the sorts of things that an algorithm problem might ask you to do are so varied, there's no unified technique that will allow you to solve all of them.
而且因为算法问题可能要求你做的事情是多种多样的，所以没有统一的技术可以让你解决所有问题。
And this is different from what you see in a lot of classes, when you're learning linear algebra they talk about how do you solve systems of linear equations.
这与你在很多课程中看到的不同，当你学习线性代数时，他们会谈到你如何解决线性方程组。

他们教你一些技巧，比如行减少，然后你就完成了。
You just sort of need to practice it, and you can solve any system of linear equations.
你只需要练习它，你就可以解决任何线性方程组。
They give you a system of linear equations, you turn the crank on this row reduction technology and out pops an answer.
它们为您提供了一个线性方程组，您可以在此行减速技术上转动曲柄并弹出答案。
For algorithms there isn't that sort of thing.
对于算法，没有那种东西。
There's no general procedure where I give you an algorithms problem and you sort of plug it into this machine and turn a crank and out pops a good algorithm for it.
没有一般的程序，我给你一个算法问题，你可以把它插入这台机器并转动一个曲柄，然后弹出一个很好的算法。
And this makes it hard to teach.
这使教学变得困难。
If there was such a thing, we could just teach you, here's this thing that you do.
如果有这样的事情，我们可以教你，这就是你做的事情。
You do this, and you'll have a good algorithm for any problem you might run into.
你这样做了，对于你可能遇到的任何问题，你都会有一个很好的算法。
And it's harder than that.
它比那更难。
I mean, sometimes, in order to find a good algorithm, it requires that you have a unique insight.
我的意思是，有时候，为了找到一个好的算法，它需要你有一个独特的见解。
You're working on some problem that no one's ever looked at before.
你正在解决以前没有人看过的一些问题。
In order to find a good algorithm for it, you need to come up with some clever idea that no one else has ever come up with before.
为了找到一个好的算法，你需要想出一些其他人从未想过的聪明的想法。
This is why sort of algorithms are so well studied, why they're such an active field of research.
这就是为什么有些算法得到了很好的研究，为什么它们是如此活跃的研究领域。
There are still so many different new things yet to be discovered there.
还有很多不同的新事物尚待发现。
And we certainly can't teach you things that haven't been discovered yet.
我们当然不能教你尚未发现的东西。

而且我们也无法教你根据你作为程序员生活中遇到的问题而定制的东西。
So since we can't teach you everything you need to know about how to solve all of your algorithm problems, what can we teach you? Well, there are sort of two things.
因为我们无法教你如何解决所有算法问题所需的一切，我们能教你什么？嗯，有两件事。
One thing that we can definitely give you is practice designing algorithms.
我们可以肯定的一件事就是练习设计算法。
We're going to have lots of homework problems with lots of things for you to work on, and this will give you practice, how do you, given a problem you haven't seen before, come up with a good algorithm for it? Once you have the algorithm, how do you implement it and make sure everything works and runs reasonably well? That's something you can practice.
我们会有很多功课需要你做很多事情，这会给你练习，你怎么样，给出你以前没见过的问题，想出一个好的算法呢？一旦你有了算法，你如何实现它并确保一切正常并且运行得相当好？这是你可以练习的东西。
And it turns out that for the type of problems where they're sort of very general and can be many different things, I mean, it's possible to solve a lot of them, and one of the ways to be able to solve them is practice.
事实证明，对于那些非常普遍且可能有很多不同事物的问题类型，我的意思是，它可以解决很多问题，其中一种解决问题的方法就是实践。
But we're also going to do more.
但我们也会做更多。
We're not just going to throw you in the deep end and say, try to swim, try to program all of these algorithms.
我们不仅会让你陷入困境，还要试着游泳，尝试编程所有这些算法。
There is something useful.
有一些有用的东西。
We can't teach you a generic procedure that will solve any algorithms problem for you.
我们无法教你一个能解决任何算法问题的通用程序。
But what we can do is we can give you some common tools.
但我们能做的就是为您提供一些常用工具。
Some very useful tools for algorithm design.
一些非常有用的算法设计工具。
And especially in this first course in our specialization we're really going to focus on helping to build up your algorithmic toolbox.
特别是在我们专业化的第一个课程中，我们将专注于帮助构建您的算法工具箱。
And in particular, this course is going to focus on three of the most common and most generally applicable algorithmic design techniques.
特别是，本课程将重点介绍三种最常见，最普遍适用的算法设计技巧。
The first of these is greedy algorithms.
第一个是贪心算法。
This is something where you're trying to construct some big object, and the way you do it is you sort of make one decision in the most greedy, locally optimal way you can.
这是你正在尝试构建一些大对象的东西，而你这样做的方式就是你可以用最贪婪的，局部最优的方式做出一个决定。
And once you've made that decision you make another decision in the most greedy, locally optimal way you can.
一旦你做出了这个决定，你就可以用最贪婪，最优化的方式做出另一个决定。
And you just keep making these decisions one at a time until you have an answer.
你只需要一次做出这些决定，直到得到答案。
And surprisingly somehow making these locally optimal decisions gives you a globally optimal solution.
令人惊讶的是，以某种方式做出这些局部最优决策为您提供全局最优解决方案
And when this happens it gives you very clean algorithms and it's great.
当发生这种情况时，它会为您提供非常干净的算法，而且非常棒。
That's the first thing we'll talk about.
这是我们要谈的第一件事。
Next, we'll talk about divide and conquer, which is a technique where you've got some big problem you're trying to solve.
接下来，我们将谈论分而治之，这是一种你正试图解决的一个大问题。

你做的是把它分成一堆小块，你解决所有的碎片，然后你把它们的答案放在一起解决原始的问题。
Finally we'll talk about dynamic programming.
最后，我们将讨论动态编程。
This is a little bit more subtle of a technique.
这是一种技术的一点点微妙。
This is what you get when you've got some sort of large problem, that has sort of a lot of, not sub-problems, but sort of related problems to it.
这就是当你遇到某种大问题时所得到的问题，它有很多问题，而不是子问题，而是一些相关的问题。
And this sort of whole family of related problems, their solutions sort of depend on one another in a particular type of way.
而这种相关问题的整个家族，他们的解决方案在某种特定类型的方式上彼此依赖。
And when you have it there's this great trick that you have, where you sort of start at the small problems at the bottom of the pile.
当你拥有它时，你就拥有了这个伟大的技巧，你可以从那里开始解决桩底问题。
And you solve all of them.
你解决了所有这些问题。
And you sort of keep track of all of your answers.
你可以跟踪所有的答案。
And you use the answers to the small problems, to build up to obtain answers to the larger and larger problems.
并且您使用小问题的答案，建立以获得更大和更大问题的答案。
So these are what we're going to talk about.
所以这些就是我们要讨论的内容。
Each of the techniques we're going to talk about, how you recognize when it applies, how do you analyze it when it applies, and some practical techniques about how to implement, how to use them.
我们将讨论的每种技术，如何识别它何时应用，如何应用它时如何进行分析，以及一些关于如何实施，如何使用它们的实用技术。
All that good stuff.
所有那些好东西。
So there's one other thing before we let you go into the fun world of greedy algorithms that you should keep in mind throughout this course, and that's that there are these, maybe, different levels of algorithm design.
所以在我们让你进入贪婪算法的有趣世界之前还有另外一件事，你应该在整个课程中牢记这一点，那就是有这些，也许是不同级别的算法设计。
There's sort of different levels of sophistication that go into it.
其中有各种不同的复杂程度。
At sort of the very lowest level, or top of this slide, I guess, there is the naive algorithm.
在这个幻灯片的最低级别或顶部，我猜，有一个天真的算法。
This is sort of a thing where you take the definition of a problem and you turn it into an algorithm, and we saw this for Fibonacci numbers and greatest common divisors.
这是一个你接受问题定义并将其转化为算法的东西，我们看到了斐波纳契数和最大公约数。
You sort of interpreted the definition of the thing you wanted to compute as an algorithm, and you were done.
您可以将您想要计算的事物的定义解释为算法，并且您已经完成了。
Now, these things are often very slow, as we saw.
现在，正如我们所看到的，这些事情往往非常缓慢。
Often they look like in order to find the best way of doing something, we enumerate all ways to do it, and then figure out which one's the best.
通常他们看起来是为了找到最好的做事方式，我们列举所有方法来做，然后找出哪一个是最好的。
On the other hand, these are slow, but it's often a good idea to first come up with a naive algorithm, just make sure you have some algorithm that works.
另一方面，这些都很慢，但首先想出一个天真的算法通常是一个好主意，只要确保你有一些有效的算法。
Sometimes this works well and often you can just be done with it.
有时候这种方法很有效，通常你可以用它完成。
Other times, it's too slow, but at least you made sure that you understood what problem you were working on and have something that runs.
其他时候，它太慢了，但至少你确定你明白你正在做什么问题并且有一些运行的东西。
But after that, the next thing that you want to do, if this naive algorithm is too slow, is you try and look at your tool box.
但在那之后，你要做的下一件事，如果这个天真的算法太慢，你试着看看你的工具箱。
You say, are there any standard techniques that I know that apply here? Maybe there's a greedy algorithm that solves this problem, or maybe I have to use a dynamic program.
你说，有没有我知道适用的标准技术？也许有一个贪婪的算法可以解决这个问题，或者我可能需要使用动态程序。
But if you can find one of these standard techniques that work, often that doesn't involve too much effort on your part, and gives you something that works pretty well.
但是如果你能找到其中一种有效的标准技术，通常不需要你付出太多努力，并且能给你一些非常好的东西。
Now once you have something that works, you often want to optimize it.
现在，一旦你有一些有用的东西，你经常想要优化它。
And there are lots of ways to improve an existing algorithm.
并且有很多方法可以改进现有的算法。
Reduce the runtime from n-cubed to n-squared or n-squared to n.
将运行时间从n-cubed减少到n-squared或n-squared到n。
And to do this, there are just a whole bunch of things.
要做到这一点，只有很多东西。
Maybe sometimes you could just sort of rearrange the order in which you do the operations to cut out some of the work that you do.
也许有时你可能只是重新排列你执行操作的顺序，以削减你做的一些工作。
Sometimes you have to introduce a data structure to speed things up.
有时您必须引入数据结构以加快速度。

有很多方法可以做到这一点。
We'll talk a little bit about how this works.
我们将谈谈它是如何工作的。
And these three levels are things that you should be comfortable with and able to apply pretty well by the end of this course.
这三个级别是你应该感到舒服的，并且能够在本课程结束时很好地应用。
However, sometimes these three are not enough.
但是，有时这三个还不够。
Sometimes a naive algorithm is just too slow, the standard tools don't apply, there's nothing that you can really optimize to improve things.
有时一个天真的算法太慢，标准工具不适用，没有什么可以真正优化来改进。
Sometimes in order to get a workable algorithm, what you need is magic.
有时为了获得可行的算法，你需要的是神奇的。
You need some unique insight that no one else has ever had before.
你需要一些以前从未有过的独特洞察力。
You need some sort of clever new idea and these, there's only so much we can do to teach you how to produce magic.
你需要一些聪明的新想法，这些，我们可以做的就是教你如何制作魔法。
We will show you some examples of things that really did have clever ideas that maybe you can't reproduce the thought process like, how do you come up with this crazy idea, that just happens to make this work? You should at least be able to appreciate the sort of thought that goes into this sort of thing.
我们将向您展示一些事实，其中确实有一些聪明的想法，也许您无法重现思考过程，例如，您如何想出这个疯狂的想法，这恰好使这项工作成功？你至少应该能够理解这种事情的那种思想。
In any case it's something to keep in mind when looking on that, when thinking about our problems, and what sort of things are expected of you.
在任何情况下，在考虑问题时，要考虑到我们的问题，以及对您的期望是什么样的事情，请记住这一点。
In any case, that is basically it for the introductory segment.
在任何情况下，这基本上都是介绍性部分。
We've talked a lot about sort of why algorithms are important and given you some examples.
我们已经谈了很多关于为什么算法很重要并给你一些例子的原因。
We've talked about asymptotic notation, but now it's time to let you go to the rest of the course.
我们已经谈到了渐近符号，但是现在是时候让你去学习其他课程了。
The rest of the course will keep giving you exercises to hone your skills, and each unit of this course will cover one of these major techniques.
本课程的其余部分将继续为您提供练习以磨练您的技能，本课程的每个单元都将涵盖其中一项主要技巧。
After I leave you with the end of the introduction, Michael will pick up and talk to you about greedy algorithms.
在我离开你的介绍结束后，迈克尔将接听并与你谈论贪婪的算法。
Next off, Neil will talk to you about divide and conquer.
接下来，尼尔将与你谈论分而治之。
Finally, Pavel will have a unit on dynamic programming.
最后，Pavel将有一个关于动态编程的单元。
Each of these, they will talk to you about where the technique applies, how to analyze it, how to implement it, all that good stuff.
其中每一个，他们都会与您讨论技术应用的位置，如何分析，如何实施，以及所有好的东西。
But this is where I leave you, I hope you enjoyed the introduction, and I will put you in Michael's very capable hands to start learning about greedy algorithms starting in the next lecture.
但这就是我离开你的地方，我希望你喜欢这个介绍，我会让你在迈克尔的能力很强的手中开始学习贪婪的算法，从下一讲开始。
So, until then, farewell.
所以，在那之前，告别。
------------- 19 -------------
01号码最大
Hi, I'm Michael Levin and together we will study Greedy Algorithms.
嗨，我是迈克尔莱文，我们将一起研究贪婪算法。
They are some of the simplest algorithms that exist and they usually seem a pretty natural way to try solving a problem.
它们是存在的一些最简单的算法，它们通常似乎是尝试解决问题的一种非常自然的方式。
We will start with a few examples of problems that can be solved by greedy algorithms, just to illustrate how they work.
我们将从贪婪算法可以解决的一些问题示例开始，只是为了说明它们是如何工作的。
And our very first problem is a problem about largest number.
我们的第一个问题是关于最大数量的问题。

对于这个问题，你可能会自己想出一个贪婪的算法，因为这真的是很自然的事情。
So imagine this situation.
想象一下这种情况。
You are trying to get a job at a company and you already had a few interviews, and everything went well.
你正试图在一家公司找到一份工作而且你已经接受过一些采访，一切都很顺利。
Now you have your final interview with the boss, and he tells you that he will give you an offer.
现在你对老板进行了最后的采访，他告诉你他会给你一个报价。
But instead of negotiating your salary with you, he will give you a few pieces of paper with digits written on them.
但是，他不会和你谈判你的工资，而是会给你一些纸上写着数字的纸。
And your task will be to arrange those digits in a row, so that when you read the number from left to right, that will be your salary.
你的任务是将这些数字排成一排，这样当你从左到右阅读这个数字时，这就是你的工资。
So basically, you have a problem.
所以基本上，你有一个问题。
Given a few digits, to arrange them in the largest possible number.
给出几位数，以尽可能多的数量排列它们。
And there are a few examples of such numbers on the slide.
幻灯片上有一些这样的数字示例。
So what do you think will be the correct answer to this problem? And of course, the correct answer is 997531.
那么您认为这个问题的正确答案是什么？当然，正确答案是997531。
And it's pretty obvious that you should arrange numbers from the largest to the smallest, from left to right.
而且很明显，你应该从左到右排列从最大到最小的数字。
But let's look at how the greedy algorithm does that.
但让我们来看看贪心算法是如何做到的。
So, the Greedy Strategy is start with a list of digits then find the maximum digit in the list.
因此，贪婪策略从一个数字列表开始，然后找到列表中的最大数字。
Append it to the number and remove it from the list.
将其附加到号码并将其从列表中删除。
And then repeat this process until there are no digits left in the list.
然后重复此过程，直到列表中没有剩余数字。
So on the next step we will find the largest digit, which is again 9.
因此，在下一步，我们将找到最大的数字，即9。
We'll append it to the number to the right and remove it from the list.
我们会将其附加到右侧的数字并将其从列表中删除。
Then we will find 7 as the largest digit appended to the right and remove it from the list.
然后我们将找到7作为右侧附加的最大数字并将其从列表中删除。
And then we'll continue with 5, 3, and 1.
然后我们将继续5,3和1。
And then we get the correct answer, 997531.
然后我们得到正确答案，997531。
And in the next video, we will design an algorithm to find the minimum number of refuels during a long journey by car.
在下一个视频中，我们将设计一种算法，以便在长途旅行中找到最少的加油次数。
We will see similarities between these two problems, largest number problem and car refueling problem.
我们将看到这两个问题，最大数量问题和汽车加油问题之间的相似之处。
And we will define how greedy algorithms work in general.
我们将定义贪婪算法的一般工作方式。
------------- 20 -------------
02汽车加油
Hi.
你好。
In this video, we will consider the problem to find the minimum number of refills during a long journey by a car.
在这段视频中，我们将考虑在汽车长途旅行中找到最小补充次数的问题。
You will see the similarities between this problem and the largest number problem from the previous video.
您将看到此问题与上一个视频中最大数量问题之间的相似之处。
By the end, you will be able to describe how greedy algorithms work in general and define what is a safe move and a subproblem.
最后，您将能够描述贪婪算法的一般工作方式，并定义什么是安全移动和子问题。
Consider the following problem.
考虑以下问题。
You have a car such that if you fill it up to full tank, you can travel with it up to 400 kilometers without refilling it.
你有一辆汽车，如果你把它装满满罐，你可以带它行驶400公里而不需要重新加油。
And you need to get from point A to point B, and the distance between them is 950 kilometers.
你需要从A点到B点，它们之间的距离是950公里。
Of course, you need to refill on your way, and luckily, there are a few gas stations on your way from A to B.
当然，你需要在路上补充，幸运的是，从A到B的路上有几个加油站。
These are denoted by blue circles, and the numbers above them mean the distance from A to the corresponding gas station along the way from A to B.
这些用蓝色圆圈表示，它们上面的数字表示从A到B的路径上从A到相应加油站的距离。
And you need to find the minimum number of refills to get from A to B.
而且你需要找到从A到B的最小重新填充次数。
One example of such route is to get from point A to the first gas station, 200 kilometers, then to get from first station to the third gas station, 350 kilometers distance.
这种路线的一个例子是从A点到达第一个加油站，200公里，然后从第一个站到达第三个加油站，距离为350公里。
Then from third gas station to the fourth gas station, 200 km, and then from the fourth gas station to B, 200 kilometers.
然后从第三加油站到第四加油站，200公里，然后从第四加油站到B，200公里。
But that's not optimal.
但那不是最佳选择。
We can do better.
我们可以做得更好。
Here is another route, which only uses two refills.
这是另一条路线，只使用两次续航。

我们从A到第二个加油站，不到400公里，然后我们从第二个加油站到达第四个加油站，再次不到400公里。
And then, from the fourth gas station to B, only 200 kilometers.
然后，从第四个加油站到B，只有200公里。
And this route uses only 2 refills, and it turns out that in this problem, the minimum number of refills is exactly 2.
而这条路线只使用了2次补充，结果发现在这个问题中，最小补充次数正好是2次。
More formally, we have the following problem.
更正式地说，我们有以下问题。
As the input, we have a car which can travel at most L kilometers, where L is a parameter if it's filled up to full tank.
作为输入，我们有一辆车可以行驶最多L公里，其中L是一个参数，如果它填满了满罐。
We have a source and destination, A and B, and we have n gas station at distances from x1 to xn in kilometers, from A along the path from A to B.
我们有一个源和目的地，A和B，我们有一个加油站，距离从x1到xn，以千米为单位，从A沿着从A到B的路径。
And we need to output the minimum number of refills to get from A to B, not counting the initial refill at A.
我们需要输出从A到B的最小重新填充次数，不计算A处的初始重新填充。
We want to solve this problem using a greedy strategy, and greedy strategy in general is very easy.
我们想用贪婪的策略解决这个问题，一般来说贪婪策略很容易。

你首先做出一些贪婪的选择，然后你将问题减少到一个较小的子问题，然后你迭代直到没有任何问题。

在这个特定问题中，有几种不同的方法可以做出贪婪的选择。
For example, you can always refill at the closest gas station to you.
例如，您可以随时在最近的加油站重新加油。
Another way is to refill at the farthest reachable gas station, and by reachable, I mean that you can get from your current position to this gas station without refills.
另一种方法是在最远的可到达的加油站重新加油，并且可以到达，我的意思是你可以从你当前的位置到达这个加油站，而无需重新加油。
Another way is, for example, to go until there is no fuel and then just hope that there will be a gas station in there.
另一种方法是，例如，直到没有燃料，然后只希望那里会有一个加油站。
So what do you think is the correct strategy in this problem? And of course, the third option is obviously wrong.
那么您认为这个问题的正确策略是什么？当然，第三种选择显然是错误的。
The first option is also wrong, if you think about it, but the second option is actually correct.
第一个选项也是错误的，如果你考虑一下，但第二个选项实际上是正确的。
It will give you the optimal number of refills.
它会为您提供最佳的笔芯数量。
We will prove it later.
我们稍后会证明。
For now, let's define our greedy algorithm as the whole algorithm.
现在，让我们将贪婪算法定义为整个算法。
So we start at A and we need to get to B with the minimum number of refills.
所以我们从A开始，我们需要以最少的笔芯数到达B.
We go from A to the farthest reachable gas station G so that we can get from A to G with full tank without any refills in the middle.
我们从A到最远的可到达加油站G，这样我们可以从A到G从满油箱到达，中间没有任何加油。
And now, we try to reduce this problem to a similar problem.
现在，我们尝试将此问题减少到类似的问题。
We make G the new A, and now our problem is to get from the new A to B, again with the minimum number of refills.
我们将G作为新的A，现在我们的问题是从新的A到B，再次使用最少的笔芯。
And by definition, a subproblem is a similar problem of smaller size.
根据定义，子问题是较小尺寸的类似问题。
One example of subproblem is from the previous video.
子问题的一个例子来自前一个视频。
When we need to construct the largest number out of a list of digits, we first put the largest digits in front, and then we reduce our problem to the problem of building the largest number out of the digits which are left.
当我们需要从数字列表中构造最大数字时，我们首先将最大数字放在前面，然后我们将问题减少到构建剩余数字中最大数字的问题。
In this problem, to find the minimum number of refills on the way from A to B, the first refill at the farthest reachable gas station G.
在这个问题上，要找到从A到B的最小补充次数，在最远的可到达的加油站G进行第一次补充。
And then solve a similar problem which is a subproblem to get from G to B with the minimum number of refills.
然后解决一个类似的问题，这是一个子问题，从G到B以最少的重新填充。
Another important term is safe move.
另一个重要的术语是安全行动。
We call a greedy choice a safe move if it is consistent with some optimal solution.
如果它与一些最佳解决方案一致，我们称贪婪的选择是安全的举动。
In other words, if there exists some optimal solution in which first move is this greedy choice, then this greedy choice is called a safe move.
换句话说，如果存在一些最优解决方案，其中第一步是这种贪婪的选择，那么这种贪婪的选择被称为安全移动。
And we will prove a lemma that to refill at the farthest reachable gas station is a safe move.
我们将证明在最远的可到达的加油站重新填充是一个安全的举动。
Let us first prove it visually.
让我们首先在视觉上证明它。
Let's consider some optimal route from A to B, and let the first stop on this route to refill B at point G1.
让我们考虑从A到B的一些最佳路线，让第一站在这条路线上重新填充B点G1。
And let G be the farthest gas station reachable from A.
让G成为从A到达的最远的加油站。
If G1 and G coincide, then our lemma is proved already.
如果G1和G重合，那么我们的引理就已经证明了。
Otherwise, G1 has to be closer to A than G, because G is the farthest reachable from A, and G1 is reachable from A.
否则，G1必须比A更接近A，因为G是从A到达最远的，并且G1可以从A到达。
Now, let's consider the next stop on the optimal route, and that would be G2.
现在，让我们考虑最佳路线的下一站，那就是G2。
And the first case is that G is closer to A than G2, then the route can look like this.
第一种情况是G比G2更接近A，然后路线看起来像这样。
In this case, we can actually refill at G instead of G1, and then we will have another optimal route because it has the same number of refills and G is reachable from A.
在这种情况下，我们实际上可以在G而不是G1处重新填充，然后我们将有另一条最佳路线，因为它具有相同数量的重新填充且G可从A到达。
And G2 is actually reachable from G, because it was reachable from G1, but G is closer to G2 than G1.
并且G2实际上可以从G到达，因为它可以从G1到达，但是G比G1更接近G2。
So this is a correct route, and in this case, our lemma is proved.
所以这是一条正确的路线，在这种情况下，证明了我们的引理。
And the second case is when G2 is actually closer to A than G, and then the route can look like this.
第二种情况是当G2实际上比A更接近A时，然后路线看起来像这样。
But in this case we can avoid refilling at G1 at all and refill at G2 or even refill at G in the first place.
但是在这种情况下，我们可以完全避免在G1处重新填充并在G2处重新填充，或者甚至在G处重新填充。
And then we will reduce the number of refills of our optimal route, which is impossible.
然后我们将减少最佳路线的重新填充次数，这是不可能的。
So the second case actually contradicts our statement that we are looking at an optimal route, and we've proved our lemma.
因此，第二种情况实际上与我们的观点相矛盾，即我们正在寻找最佳路线，并且我们已经证明了我们的引理。
To recap, we consider the optimal route R with a minimum number of refills.
总结一下，我们考虑最佳路线R，最小补充次数。
We denote by G1 the position of the first refill in R, and by G2, the next stop was R, which is either a refill or the destination B.
我们用G1表示第一个替换物在R中的位置，而在G2，下一站是R，它是一个替换物或目的地B.
And by G we denote the farthest refill reachable from A, and we considered two cases.
由G我们表示从A可以到达的最远的填充物，我们考虑了两种情况。
In the first case, if G is closer than G2 to A, we can refill at G instead of G1, and it means that refill at G is a safe move.
在第一种情况下，如果G比G2更靠近A，我们可以在G而不是G1处重新填充，这意味着在G处重新填充是一个安全的举动。
Otherwise, we can avoid refill at G1.
否则，我们可以避免在G1重新填充。
So this case contradicts that the route R is the route with the minimum number of refills.
因此，这种情况与路线R是具有最小重新填充次数的路线相矛盾。
So there is no such case, and we proved our lemma.
所以没有这样的情况，我们证明了我们的引理。
And in the next lecture, we will implement this algorithm in pseudocode and analyze its running time.
在下一讲中，我们将以伪代码的形式实现该算法并分析其运行时间。
------------- 21 -------------
03汽车加油实施和分析
Hi, in this video you will learn to implement the greedy algorithm from the previous video, and analyze its running time.
嗨，在本视频中，您将学习如何实现上一个视频中的贪婪算法，并分析其运行时间。
Here we have the pseudocode for this algorithm, and the procedure is called MinRefills.
这里我们有这个算法的伪代码，程序叫做MinRefills。
And the main input to this procedure is array x.
此过程的主要输入是数组x。
From the problems statement, we know that the positions of the gas stations are given by numbers from x1 to xn.
从问题陈述中，我们知道加油站的位置由x1到xn的数字给出。
And those are measured in kilometers in terms of distance from A to the corresponding gas station along the path from A to B.
这些是以公里为单位测量的，从A到相应的加油站沿着从A到B的路径的距离。
For convenience, we actually add to array x positions of point A which is x0 and is the smallest value in the array.
为方便起见，我们实际上添加了点A的数组x位置，它是x0并且是数组中的最小值。
And point B, which is Xn plus 1, and it is the largest value in the array x.
并且B点是Xn加1，它是数组x中的最大值。
Along our route from A to B, we will visit some points.
沿着从A到B的路线，我们将访问一些点。
Of course we will start from point A.
当然我们将从A点开始。
And then we'll probably go to some gas station, refilll there.
然后我们可能去一些加油站，在那里重新装满。
And then go to another gas station and to another gas station and then to another and then at some point we will get to the point B or point x n plus 1.
然后去另一个加油站和另一个加油站再到另一个加油站，然后在某个时刻我们将到达B点或点xn加1。
So we see that we only need to store the positions in the array x.
所以我们看到我们只需要在数组x中存储位置。
We don't need to consider any positions between the elements of array x.
我们不需要考虑数组x的元素之间的任何位置。
And so, we will store in the variable currentRefill, the position in the array x where we're currently standing.
因此，我们将存储在变量currentRefill中，即我们当前所在的数组x中的位置。
And we will initialize it with 0.
我们将用0初始化它。
Because we start from point A, which is the same as x0, and has index 0 in the array x.
因为我们从点A开始，它与x0相同，并且在数组x中具有索引0。
And later currentRefill will store the index in the array x, where we're currently standing.
之后currentRefill会将索引存储在我们目前所在的数组x中。
We'll also store the answer to our problem in the variable numRefills.
我们还将在变量numRefills中存储我们问题的答案。
At each point in the execution of the algorithm, it will contain the number of refills we have already made.
在执行算法的每个点，它将包含我们已经完成的重新填充的数量。
And we initialize it with zero because the problem statement asks us to count the minimum number of refills we need to do.
我们用零初始化它，因为问题陈述要求我们计算我们需要做的最小重新填充次数。
Not counting the initial refill at point A.
不计算A点的初始补充。
So when we are standing at point A, we consider that we haven't made any refills yet.
因此，当我们站在A点时，我们认为我们尚未进行任何补充。
Then the main external while loop goes.
然后主外部while循环进行。
And it goes on while we're still to the left from point B, because then we need to go right to reach our destination B.
它继续从B点开始向左移动，因为那时我们需要向右走到目的地B.
And we check this condition with this inequality, that currentRefill is at most n.
我们用这个不等式检查这个条件，currentRefill最多是n。
This means that the position or index in the array x is at most n, and so we're to the left from point B currently.
这意味着数组x中的位置或索引最多为n，因此我们当前位于B点的左侧。
In this case we still need to go to the right.
在这种情况下，我们仍然需要向右走。
And first we save our current position in the array x in the variable lastRefill.
首先，我们在变量lastRefill中保存数组x中的当前位置。
This means that we made our lastRefill in the position currentRefill.
这意味着我们将lastRefill设置为currentRefill。
And now we need to go to the right from there, and either get to destination B or get to the rightmost reachable gas station and refill there.
现在我们需要从那里向右走，然后到达目的地B或者到达最右边的可到达加油站并在那里重新加油。
And the next internal while loop does exactly that.
而下一个内部while循环正是如此。
It gradually increases our currentRefill position in the array x until it reaches the rightmost point in the array x which is reachable from the lastRefill position.
它逐渐增加数组x中的currentRefill位置，直到它到达数组x中可从lastRefill位置到达的最右边的点。
So first we check that currentRefill position is at most n because if it is n plus 1 already it means that we reached our destination B.
所以首先我们检查currentRefill位置最多是n，因为如果它已经是n加1，那就意味着我们到达了目的地B.
And there is no point increasing it further.
没有必要进一步增加它。
If it's still to the left from B, then we'll look at the next position to the right, x currentRefill plus 1.
如果它仍然在B的左边，那么我们将查看右边的下一个位置，x currentRefill加1。
We need to check whether it's reachable from lastRefill position or not.
我们需要检查它是否可以从lastRefill位置到达。
And first we can build the distance from the lastRefill position to the currentRefill plus one position by subtracting the values of the array x.
首先，我们可以通过减去数组x的值来建立从lastRefill位置到currentRefill加上一个位置的距离。
And if this distance is at most L, then it means that we can travel this distance with full tank, without any refills.
如果这个距离最多为L，那么这意味着我们可以在满载坦克的情况下行驶这段距离，而无需任何补充。
And of course, at the lastRefill position, we could fill our tank up to the full capacity.
当然，在最后的补给位置，我们可以将我们的坦克装满。
And then we'll be able to travel for L kilometers.
然后我们将能够行驶L公里。
So, this inequality checks if actually position currentRefill plus 1 is reachable from the lastRefill position.
因此，这个不等式检查实际位置currentRefill加1是否可以从lastRefill位置到达。
If it is, we increase the value of currentRefill and go on with our internal while loop.
如果是，我们增加currentRefill的值并继续我们的内部while循环。
When we exit this internal while loop we're already maybe in the point B, or we may be in some point which is the farthest reachable gas station.
当我们退出这个内部的循环时，我们已经可能在B点，或者我们可能在某个点上，这是最远的可达加油站。
Now we compare it with our lastRefill position.
现在我们将它与lastRefill位置进行比较。
And if it turns out that it is the same, it means that we couldn't go to the right.
如果事实证明它是相同的，那就意味着我们无法走向正确。
We don't have enough fuel even to get to the next gas station.
我们甚至没有足够的燃料到达下一个加油站。
And then, we cannot return the minimum number of refills that we need to do on the way from A to B, because it is impossible to get from A to B at all.
然后，我们无法返回从A到B的路上我们需要做的最小重新填充次数，因为根本不可能从A到B。
And so we return this result IMPOSSIBLE.
所以我们返回这个结果是不可能的。
Otherwise, we moved at least a bit to the right, and then we need to see.
否则，我们至少向右移动一点，然后我们需要看到。
If we are already in the point B, we don't need to do anything else.
如果我们已经在B点，我们不需要做任何其他事情。
Otherwise, we need to refill there.
否则，我们需要在那里补充。
So, we check that we're to the left from point B with this inequality.
所以，我们检查我们是否在B点左边有这个不等式。
And if it's true then we're at some gas station and we need to refuel.
如果这是真的那么我们就在加油站，我们需要加油。
So we increase the numRefills variable by one.
所以我们将numRefills变量增加1。
And then we return to the start of our external while loop.
然后我们回到外部while循环的开始。
And there we again check if we're to the left from point B we need another iteration.
然后我们再次检查我们是否从B点向左，我们需要另一次迭代。
And if currentRefill is already n plus 1, then we've reached point B and we need to exit the external while loop.
如果currentRefill已经是n加1，那么我们已经到达了B点，我们需要退出外部while循环。
And in that case, we just return the answer which is number of refills we've made so far.
在这种情况下，我们只返回答案，这是我们迄今为止所做的补充数量。
We've implemented the greedy algorithm from the previous lecture.
我们已经实现了上一讲的贪婪算法。
Now let's analyze its running time.
现在让我们分析一下它的运行时间。
From the first look it can seem that it works in n squared time because we have the external while loop which can make n iterations and internal loop which can make n iterations.
从第一次看起来它似乎可以在n平方时间内工作，因为我们有外部while循环可以进行n次迭代，内部循环可以进行n次迭代。
So, n by n is n squared, but actually we will show that it only makes O of n actions for the whole algorithm.
所以，n乘n是n平方，但实际上我们将证明它只对整个算法产生了n个n个动作。
To prove that let's first look at the currentRefill variable.
为了证明我们首先看一下currentRefill变量。
We see that it only changes one by one here.
我们看到它只是在这里逐一改变。
And it starts from zero.
它从零开始。
And what is the largest value that it can attain? Of course, the largest value is n plus 1 because this is the largest index in the array x, and currentRefil is index in the array x.
它能达到的最大价值是多少？当然，最大值是n加1，因为这是数组x中的最大索引，而currentRefil是数组x中的索引。
So, variable currentRefil starts from zero, changes one by one.
因此，变量currentRefil从零开始，逐个变化。
And the largest value it can have is n plus 1.
它可以拥有的最大值是n加1。
It means that it is increased at most n plus 1 times which is Big-O of n.
这意味着它最多增加n加1倍，即n的Big-O。
But that's not all we do.
但这不是我们所做的全部。
Also, we increase variable numRefills here.
此外，我们在这里增加变量numRefills。
But we also increase it always one by one.
但我们也一个接一个地增加它。
It also starts from zero.
它也从零开始。
And what is the largest number that this variable can attain? Well, of course, it is n because when we have n gas stations.
这个变量可以达到的最大数字是多少？嗯，当然，这是因为我们有n个加油站。
There is no point to refuel twice at the same gas station.
没有必要在同一个加油站加油两次。
So we can refuel at most n times.
所以我们最多可以加油n次。
So variable numRefills goes from 0 to n and changes one by one.
因此，变量numRefills从0变为n并逐个变化。
So it is only changed at most n times.
所以它最多只改变了n次。
And so, it is also linear in terms of n.
因此，就n而言，它也是线性的。
And so, we have at most n plus 1 iterations of the external while loop.
因此，我们在外部while循环中最多有n加1次迭代。
Everything but the internal while loop takes there constant time.
除了内部while循环之外的所有东西都需要恒定的时间。
This assignment, this if, and this if with assignment.
这个赋值，这个if，如果有赋值的话。
And the external loop and internal loop combined also spend at most linear time of iterations.
并且外部循环和内部循环组合也花费在最多线性迭代时间。
Because they change variable currentRefill and it changes at most linear number of times.
因为它们改变了变量currentRefill并且它最多改变了线性次数。
So all in all our algorithm works in Big-O n time.
因此，总而言之，我们的算法在Big-O n时间工作。
Let's go through this proof once again.
让我们再次通过这个证明。
The Lemma says that the running time of the whole algorithm is big O of n.
引理说整个算法的运行时间是n的大O.
And we prove this by first noticing that the currentRefill variable changes only from zero to at most n plus 1.
我们通过首先注意到currentRefill变量仅从零变化到最多n加1来证明这一点。
And the change is always one by one.
而变化总是一个接一个。
That the numRefills variable changes from zero to at most n.
numRefills变量从零变为最多n。
And it also changes one by one.
它也一个接一个地改变。
So, both these variables are changed Big-O of n times.
因此，这两个变量都改变了n次的Big-O。
And everything else that happens is constant time.
其他一切都是不变的时间。
Each iteration of the external loop, and there are at most n plus 1 iterations of the external loop.
外部循环的每次迭代，外部循环最多有n加1次迭代。
Thus, our algorithm works in linear time.
因此，我们的算法在线性时间内工作。
In the next video, we will review what we've learned about greedy algorithms in general.
在下一个视频中，我们将回顾一下我们对贪婪算法的了解。
------------- 22 -------------
04贪心算法的主要成分
Hi.
你好。
In this video, we will briefly review the main ingredients of greedy algorithms and the first of them is reduction to a subproblem.
在本视频中，我们将简要回顾贪婪算法的主要成分，其中第一个是简化为子问题。
Basically, when you have some problem, you make some first move and thus reduce your problem to a similar problem, but which is smaller.
基本上，当你遇到一些问题时，你先做一些动作，从而将你的问题减少到类似的问题，但这个问题要小一些。
For example, you have fewer digits left or fewer gas stations left in front of you and this similar problem, which is smaller is called a subproblem.
例如，您剩下的数字较少或者前面留下的加油站较少，这个类似的问题较小，称为子问题。
Another key ingredient is a safe move and the move is called safe if it is consistent with some optimal solution.
另一个关键因素是安全移动，如果它与某些最佳解决方案一致，则称其为安全移动。
In other words, if there exists some optimal solution in which the first move is the same as your move, then your move is called a safe move and not all first moves are actually safe.
换句话说，如果存在一些最佳解决方案，其中第一个移动与您的移动相同，那么您的移动被称为安全移动，并非所有第一步移动实际上都是安全的。
For example, to go until there's no fuel is not a safe move in the problem about car fueling.
例如，直到没有燃料在汽车加油问题上不安全。
And often, greedy moves are also not safe, for example, to get to the closest gas station and refuel at it is not a safe move while to get to the farthest gas station and refuel there is a safe move.
通常情况下，贪婪的举动也是不安全的，例如，到达最近的加油站加油并不是一个安全的举动，而到达最远的加油站加油有一个安全的举动。
Now the general strategy of solving a problem goes like this.
现在解决问题的一般策略是这样的。
First, you analyze the problem and you come up with some greedy choice and then the key thing is to prove that this greedy choice is a safe move and you really have to prove it.
首先，你分析问题并提出一些贪婪的选择，然后关键是要证明这个贪婪的选择是一个安全的举动，你真的必须证明它。
Because, otherwise, you can come up with some greedy choice and then come up with a greedy algorithm and then even implement it and test it and try to submit it in the system.
因为，否则，你可以提出一些贪婪的选择，然后提出一个贪婪的算法，然后甚至实现它并测试它并尝试在系统中提交它。
Only to learn that the algorithm is incorrect, because the first move is actually not a safe move and there are cases in which this first move is not consistent with any optimal solution.
只是了解算法是不正确的，因为第一步实际上不是一个安全的举动，并且有些情况下，这第一步与任何最佳解决方案都不一致。
And in that case, we will have to invent a new solution and implement it from scratch.
在这种情况下，我们将不得不发明一种新的解决方案并从头开始实施。
All the work you've done before will be useless.
你之前完成的所有工作都是无用的。
So please prove your algorithms and prove that the first move is a safe move.
因此，请证明您的算法，并证明第一步是安全的举动。
When you prove that, you reduce a problem to a subproblem.
当您证明这一点时，您可以将问题减少到子问题。
And hopefully, that is a similar problem, problem of a same kind and then you start solving this subproblem the same way.
并且希望，这是一个类似的问题，同一类问题然后你开始以同样的方式解决这个子问题。
You make your greedy choice and you reduce it to subproblem, and you iterate until there are no problems left or until your problem is so simple that you can just solve it right away.
你做出贪婪的选择并将其减少到子问题，然后迭代直到没有任何问题或者直到你的问题如此简单以至于你可以马上解决它。
And in the next lessons, we will apply greedy algorithms to solve more difficult problems.
在接下来的课程中，我们将应用贪心算法来解决更多难题。
------------- 23 -------------
01庆祝派对问题
Hi, in this lesson we will discuss the problem of organizing children into groups.
嗨，在本课中，我们将讨论将儿童组织成小组的问题。
And you will learn that if you use a naive algorithm to solve this problem, it will work very, very slowly, because the running time of this algorithm is exponential.
并且您将了解到，如果您使用朴素算法来解决此问题，它将非常非常缓慢地工作，因为此算法的运行时间是指数级的。
But later in the next lesson, we will be able to improve the training time significantly by coming up with a polynomial time algorithm.
但是在下一课的后面，我们将通过提出多项式时间算法来显着改善训练时间。
Let's consider the following situation.
让我们考虑以下情况。
You've invited a lot of children to a celebration party, and you want to entertain them and also teach them something in the process.
你邀请了很多孩子参加庆祝派对，你想要招待他们，并在这个过程中教他们一些东西。
You are going to hire a few teachers and divide the children into groups and assign a teacher to each of the groups this teacher will work with this group through the whole party.
您将雇用一些教师并将孩子分成小组，并为每个小组分配一名教师，该老师将通过整个小组与该小组一起工作。
But you know that for a teacher to work with a group of children efficiently children of that group should be of relatively the same age.
但是你知道，对于一个老师与一群孩子一起工作，这个群体的孩子应该是相对年龄相同的。
More specifically age of any two children in the same group should differ by at most one year.
更具体地说，同一组中任何两个孩子的年龄应至少相差一年。
Also, you want to minimize the number of groups.
此外，您希望最小化组的数量。
Because you want to hire fewer teachers, and spend the money on presents and other kinds of entertainment for the children.
因为你想雇用更少的老师，并为孩子们花钱买礼物和其他类型的娱乐。
So, you need to divide children into the minimum possible number of groups.
因此，您需要将子项划分为尽可能少的组。
Such that the age of any two children in any group differs by at most one year.
这样任何一组中任何两个孩子的年龄最多相差一年。
Now, let's look at the pseudo code for the naive algorithm that solves this problem.
现在，让我们看一下解决这个问题的朴素算法的伪代码。
Basically, this algorithm will consider every possible partition of the children into groups and find the partition which both satisfies the property that the ages of the children in any group should differ by at most one and contains the minimum number of groups.
基本上，该算法将孩子的每个可能的分区考虑成组，并找到满足任何组中的孩子的年龄应该最多相差一个并且包含最小组数的属性的分区。
We start with assigning the initial value of the number of groups to the answer m and this initial value is just the number of children.
我们首先将组数的初始值分配给答案m，这个初始值只是孩子的数量。
Because we can always divide all the children into groups of one, and then of course each group has only one child so the condition is satisfied.
因为我们总能将所有孩子分成一组，然后每组只有一个孩子，所以条件得到满足。
Then we consider every possible partition of all children into groups.
然后我们将所有孩子的每个可能的分区都考虑成组。
The number of groups can be variable, so this is denoted by a number k, and we have groups G1, G2 and up to Gk.
组的数量可以是变量，因此用数字k表示，我们有G1，G2组和Gk组。
And then we have a partition, we first need to check whether it's a good partition or not.
然后我们有一个分区，我们首先需要检查它是否是一个好的分区。
So, we have a variable good which we assigned to true initially, because we think that maybe this partition will be good.
所以，我们有一个变量商品，我们最初分配给true，因为我们认为这个分区可能会很好。
But then we need to check for each group whether it satisfies our condition or not.
但是我们需要检查每个组是否满足我们的条件。
So, we go in a for group with index i of the group from 1 to k, and then we consider the particular group GI, and we need to determine whether all the children in this group differ by at most 1 year, or there are two children that differ more.
所以，我们进入一个组中索引为i的组，从1到k，然后我们考虑特定的组GI，我们需要确定这组中的所有孩子是否相差最多1年，或者有两个孩子有所不同。
To check that, it is sufficient to compare the youngest child with the oldest child.
要检查这一点，将最小的孩子与最大的孩子进行比较就足够了。
If their ages differ more than by one, then the group is bad.
如果他们的年龄差异超过1，那么这个群体就很糟糕。
Otherwise, every two children differ by at most one year, so the group is good.
否则，每两个孩子最多相差一年，所以小组很好。
And so we go through all the groups in a for loop.
所以我们在for循环中遍历所有组。
If at least one of the groups is bad, then our variable good will contain value false by the end.
如果至少有一个组是ba d，那么我们的变量good将在结尾处包含false值。
Otherwise, all the groups are good, and the variable good will contain value true.
否则，所有组都是好的，变量good将包含值true。
So, after this for loop, we check the value of the variable good, and if it's true, then we improve our answer.
因此，在这个for循环之后，我们检查变量good的值，如果它是真的，那么我们改进我们的答案。
At least try to improve it.
至少尝试改进它。
With a minimum of its current value and the number of the groups in the current partition.
使用当前分区的最小值和当前分区中的组数。
And so, by the end of the outer for loop which goes through all the partitions, our variable m will contain the minimum possible number of groups in a partition that satisfies all the conditions.
因此，在遍历所有分区的外部for循环结束时，我们的变量m将包含满足所有条件的分区中的最小可能组数。
It is obvious that this algorithm works correctly because it basically considers all the possible variants and selects the best one from all the variants which satisfy our condition on the groups.
很明显，这种算法可以正常工作，因为它基本上考虑了所有可能的变体，并从满足我们条件的所有变量中选择最佳变量。
Now, let us estimate the running time of this algorithm.
现在，让我们估算一下这个算法的运行时间。
And I state that the number of operations that this algorithm makes is at least 2 to the power of n, where n is the number of children in C.
我说这个算法所做的操作次数至少是n的幂，其中n是C中的子节点数。
Actually, this algorithm works much slower and makes much more operations than 2 to the power of n, but we will just prove this lower bound to show that this algorithm is very slow.
实际上，这个算法运行速度要慢得多，并且比n的幂要多运行2次，但我们只是证明这个下限表明这个算法非常慢。
To prove it, let's consider just partitions of the children in two groups.
为了证明这一点，让我们考虑两组儿童的分区。
Of course there are much more partitions than that.
当然，有更多的分区。
We can divide them in two, three, four, and so on.
我们可以将它们分成两个，三个，四个等等。
Much more groups.
更多的团体。
But, let's just consider partitions in two groups and prove that even the number of such partitions is already at least two to the power of n.
但是，让我们只考虑两组中的分区，并证明即使这样的分区数量已经至少是n的幂的两倍。
Really, if C is a union of two groups, G1 and G2, then basically we can make such partition for any G1 which is a subset of such C of all children.
实际上，如果C是两个组G1和G2的联合，那么基本上我们可以对任何G1进行这样的分区，这是所有孩子的这种C的子集。
For any G1, just make group G2 containing all the children which are not in the first group.
对于任何G1，只需使组G2包含不在第一组中的所有子项。
And then all the children will be divided into these two groups.
然后所有的孩子将分为这两组。
So, now the size of the set of all children is n.
所以，现在所有孩子的大小都是n。
And if you want to compute the number of possible groups G1 then we should note that each item of the set, or each child, can be either included or excluded from the group G1.
如果你想计算可能的组G1的数量，那么我们应该注意，该组或每个孩子的每个项目可以包括在G1组中或从组G1中排除。
So, there can be 2 to the power of n different groups G1.
因此，n个不同组G1的功率可以为2。
And so there are at least 2 to the power of n partitions of the set of all children in two groups.
因此，两组中所有孩子的n个分区的权力至少为2。
and it means that our algorithm will do at least 2 to the power of n operations because this considers every partition.
这意味着我们的算法将至少执行2次n次操作的功能，因为这会考虑每个分区。
Among all the partitions, there are all the partitions into two groups.
在所有分区中，将所有分区分为两组。
So, how long will it actually work? We see that the Naive algorithm works in time Omega (2n), so it makes at least 2 to the power of n operations.
那么，它实际工作多长时间？我们看到Naive算法在时间Omega（2n）中工作，因此它使n次操作的功率至少为2。
And for example for just 50 children this is at least 2 to the power of 50 or the larges number which is on the slide.
例如，对于仅50个孩子，这至少是2的50的幂或幻灯片上的大数。
This is the number of operations that we will need to make and I estimate that on a regular computer, this will take at least two weeks for you to compute this if this was exactly the number of operations that you would need.
这是我们需要进行的操作次数，我估计在普通计算机上，如果这正是您需要的操作数，则至少需要两周的时间才能计算出来。
So, it works really, really slow.
所以，它真的非常慢。
But in the next lesson we will improve this significantly.
但在下一课中，我们将大大改善这一点。
------------- 24 -------------
02分组儿童的有效算法
Hi, in this lesson you will learn how to solve the problem of organizing children into groups more efficiently.
嗨，在本课中，您将学习如何更有效地解决将儿童组织成团体的问题。
Most specifically, we will come up with a polynomial time algorithm for this problem as opposed to the exponential type algorithm from the previous lesson.
最具体地说，我们将针对此问题提出一种多项式时间算法，而不是上一课中的指数型算法。
But in order to do this, we first need to do a very important thing that you should probably do every time before solving an algorithmic problem.
但是为了做到这一点，我们首先需要做一个非常重要的事情，你应该在解决算法问题之前每次都做。
You should reformulate it in mathematical terms.
你应该用数学术语重新表述它。
For example, in this problem we will consider points on the line instead of children.
例如，在这个问题中，我们将考虑线上的点而不是孩子。
For example, if we have a child of age three and a half years we will instead consider a point on the line with coordinate 3.5 and if we have another child of age 6, we will instead consider a point with coordinate 6 on the line.
例如，如果我们有一个三岁半的孩子，我们将考虑坐标3.5上的一个点，如果我们有另一个6岁的孩子，我们将考虑一个坐标为6的点。
Now, what do groups of children correspond to? If we have a group of children, it consists of several children and several points on the line correspond to this group and the fact that the age of any two children in the group differs by at most one, means that there exists a segment of length one on this line that contains all those points.
现在，孩子群体对应的是什么？如果我们有一组孩子，它由几个孩子组成，并且该行上的几个点对应于该组，并且该组中任何两个孩子的年龄最多相差一个这一事实意味着存在一段长度这一行包含所有这些点。
Now the goal becomes to select the minimum possible number of segments of length one, such that those segments cover all the points.
现在，目标是选择长度为1的最小可能段数，使得这些段覆盖所有点。
Then, if we have such segments, we can just take all the points from that segment in the same group, and any two children in the group who differ by, at most, one year.
然后，如果我们有这样的片段，我们可以从同一组中的该片段获取所有点，并且该组中的任何两个孩子最多相差一年。
Now let's look at an example.
现在让我们看一个例子。
We have a line with a few points on it and we want to cover all the points with segments of length one.
我们有一条线上有几个点，我们希望用长度为1的段覆盖所有点。
Here is one example of such covering.
这是这种覆盖的一个例子。
All the segments on the picture are of the same length and we consider that this is length one of this line.
图片上的所有段都具有相同的长度，我们认为这是该行的长度之一。
This is not the optimal solution because below there is another example of covering and we have only three segments and they still cover all the points.
这不是最佳解决方案，因为下面还有另一个覆盖示例，我们只有三个段，它们仍然覆盖所有点。
Now we want to find a way to find the minimum possible number of segments to cover all the points in any configuration.
现在，我们想要找到一种方法来查找最小可能的段数，以涵盖任何配置中的所有点。

我们希望使用贪婪算法来做到这一点，你可能记得从以前的教训中得出一个贪婪的算法，你需要做一个贪婪的选择，并证明这个贪婪的选择是一个安全的举动。
I state that in this problem, safe move is to cover the leftmost point with a segment of length one which starts or has left end in this point.
我声明在这个问题中，安全移动是用一个长度为1的段来覆盖最左边的点，该段在此点开始或已经结束。
To prove that this is really a safe move, we need to prove that there exists an optimal solution with the minimum possible number of unit length segments such that one of the segments has its left end in the leftmost point.
为了证明这确实是一个安全的举动，我们需要证明存在一个最佳解决方案，其中单位长度段的最小可能数量使得其中一个段的左端位于最左边的点。
Let's prove that.
让我们证明一下。
To do that, let's consider any optimal solution of a given problem with a given point.
为此，让我们考虑给定点的给定问题的任何最优解。
Let's consider the leftmost point colored in green.
让我们考虑最左边的点是绿色的。
It is covered by some segment.
它被某些部分覆盖。
Colored in red.
红色。
Now, let's move this red segment to the right until it's left end is in this leftmost point.
现在，让我们将这个红色部分向右移动，直到它的左端位于这个最左边的点。
I say that we didn't miss any of the points in the process, because this green point is the leftmost point so there are no points to the left from it and while we are moving the segment to the right, we didn't miss any of the points.
我说我们没有错过这个过程中的任何一点，因为这个绿点是最左边的点，所以左边没有点，当我们向右移动段时，我们没有错过任何一点。
It means that what we have now is still a correct covering because all of the points are still covered and the number of segments in this covering is the same as in some optimal solution from which we started and that means that it is also an optimal covering.
这意味着我们现在所拥有的仍然是一个正确的覆盖，因为所有的点仍然被覆盖，并且这个覆盖中的段的数量与我们开始的一些最佳解决方案中的段数相同，这意味着它也是最佳覆盖。
So we have just found an optimal solution in which there is a segment which starts in the leftmost point.
所以我们刚刚找到了一个最优解，其中有一个段从最左边开始。
So, we proved that covering the leftmost point with a segment which starts in it is a safe move.
因此，我们证明用一个从其开始的片段覆盖最左边的点是一个安全的举动。
Now that we have a safe move, let's consider what happens after it.
现在我们已经安全行动，让我们考虑一下之后会发生什么。
We have the leftmost point covered, and also maybe some other points covered.
我们覆盖了最左边的点，也可能包含其他一些要点。
So we don't need to consider these points anymore.
所以我们不再需要考虑这些点了。
We are not interested in them and we need to cover all the other points with the minimum possible number of unit length segments.
我们对它们不感兴趣，我们需要用尽可能少的单位长度段来覆盖所有其他点。
So this is the same kind of problem which we started with, so this is a subproblem.
所以这是我们开始的同类问题，所以这是一个子问题。
Basically it means that we have a greedy algorithm.
基本上它意味着我们有一个贪婪的算法。
First, make a safe move.
首先，采取安全行动。
Add a segment to the solution with the left hand starting in the leftmost point.
将一个段添加到解决方案中，左手从最左边的点开始。
Then remove all the points which are already covered by the segment from the set and if there are still points left, repeat the process and repeat this process until there are no points left in the set.
然后从集合中删除段已经覆盖的所有点，如果还有剩余点，则重复该过程并重复此过程，直到集合中没有剩余点。
------------- 25 -------------
03分析和实现高效算法
Now let us consider the pseudocode that implements this algorithm.
现在让我们考虑实现此算法的伪代码。
For the sake of simplicity we assume that the points in the input are given in sorted order from smallest to largest.
为简单起见，我们假设输入中的点以从最小到最大的排序顺序给出。
We'll start with an empty set of segments denoted by R and we start with index i pointing at the first point which is the leftmost because the points are sorted.
我们将从一个由R表示的空段开始，我们从索引i开始，指向最左边的第一个点，因为这些点是排序的。
Now we go through the points, and we find the leftmost point.
现在我们通过这些点，找到最左边的点。
Currently i is pointing to the leftmost point in the set.
目前我指向集合中最左边的点。
And at the start of the while loop i will always point to the leftmost point which is still in the set.
在while循环开始时，我将始终指向仍在集合中的最左边的点。
Now we cover it with the segment from l to r which has unit length, and the left end in the point xi, so this is a segment from xi to xi+1.
现在我们用从l到r的段来覆盖它，它具有单位长度，而左端在点xi中，所以这是从xi到xi + 1的段。
We add this segment to the solution set, and then we need to remove all the points from the set which already covered.
我们将此段添加到解决方案集中，然后我们需要从已经涵盖的集合中删除所有点。
Instead of removing the points, we will just move the pointer to the right and forget about the points, which are to the left from the pointer.
我们只是将指针向右移动而忘记指针左侧的点，而不是删除点。
So the next while loop, does exactly that.
所以下一个while循环就是这样做的。
We know that for any i that is larger than the current i, xi is to the right from the left end of the segment, because the points are sorted.
我们知道，对于任何大于当前i的i，xi是从段的左端开始的右边，因为这些点是排序的。
So if xi is also to the left from R, then it is covered by the segment.
因此，如果xi也位于R的左侧，那么它将被段覆盖。
So we just go to the right, and to the right with pointer i.
所以我们只用指针i向右移动到右边。
And while xi is less than or equal to r, we know that the point is covered.
虽然xi小于或等于r，但我们知道这一点已被涵盖。
And as soon as we find some xi which is bigger than r, it means that this point is not covered and all the points further in the array are also not covered.
一旦我们发现一些大于r的xi，就意味着这个点没有被覆盖，并且数组中的所有点也没有被覆盖。
So we stop.
所以我们停下来。
And then we repeat again the iteration of the outer while loop.
然后我们再次重复外部while循环的迭代。
Or maybe our pointer i is already out of the array of the input points.
或许我们的指针i已经超出了输入点的数组。
And then we stop and return R, which is the set of segments that we've built in the process.
然后我们停止并返回R，这是我们在流程中构建的一组段。
Now let's prove that this algorithm works in linear time.
现在让我们证明这个算法在线性时间内工作。
Indeed, index i changes just from 1 to n.
实际上，索引i从1变为n。
And we always increase it by one.
我们总是把它增加一个。
For each value of i, we add at most one segment to the solution.
对于i的每个值，我们最多将一个段添加到解决方案中。
So overall, we increase i at most n times and add at most n segments to the solution.
总的来说，我们最多增加i次n次，并且最多将n个段添加到解决方案中。
And this leads to a solution which works in Big-O of n time.
这导致了一个解决方案，它可以在大时间内运行。
Now, we had an assumption that the points in the input are already sorted.
现在，我们假设输入中的点已经排序。
What if we drop this assumption? Then we will have to sort the points first, and then apply our algorithm PointsCoverSorted.
如果我们放弃这个假设怎么办？然后我们将首先对点进行排序，然后应用我们的算法PointsCoverSorted。
Later in this module, you will learn how to sort points in time n log n.
稍后在本单元中，您将学习如何对时间n log n中的点进行排序。
Combining that with our procedure PointsCoverSorted will give you total running time of n log n.
将它与我们的程序PointsCoverSorted结合使用，可以得到n log n的总运行时间。
Now let's look at our improvement.
现在让我们来看看我们的改进。
We first implemented a straightforward solution, which worked in time at least 2 to the power of n.
我们首先实现了一个简单的解决方案，它在时间上至少能达到2的幂。
And it worked very, very slowly.
它的工作非常非常缓慢。
So that even for 50 children, we would have to spend at least 2 weeks of computation to group them.
因此，即使对于50个孩子，我们也必须花费至少2周的时间来对它们进行分组。
Our new algorithm, however, works in n log n time.
然而，我们的新算法在n log n时间内工作。
And that means that even if we had 10 million children coming to a party, it would spend only a few seconds grouping them optimally into several groups.
这意味着，即使我们有1000万儿童参加聚会，也只需要几秒钟就可以将他们最佳地分组到几个小组中。
So that's a huge improvement.
这是一个巨大的进步。
Now let's see how we went to this end.
现在让我们看看我们是如何实现这一目标的。
First, we've invented a naive solution which worked in exponential time.
首先，我们发明了一种在指数时间内起作用的天真解决方案。
It was too slow for us so we wanted to improve it.
这对我们来说太慢了，所以我们想改进它。
But to improve it, the very first important step was to reformulate it in mathematical terms.
但要改进它，第一个重要的步骤是用数学术语重新表述它。

然后我们有了一个用贪心算法解决它的想法。
So, we had to find some greedy choice and prove that it will be a safe move.
因此，我们必须找到一些贪婪的选择，并证明这将是一个安全的举措。
In this case, the safe move turns out to be to add to the solution a segment with left and in the leftmost point.
在这种情况下，安全移动结果是向解决方案添加左侧和最左侧点的段。
And then we prove that this is really a safe move.
然后我们证明这确实是一个安全的举措。
It is very important to prove your solutions before even trying to implement them.
在尝试实施它们之前证明您的解决方案非常重要。
Because otherwise, it could turn out that you implemented the solution, tried to submit it, got wrong answer or some other result, different from accepted.
因为否则，可能会导致您实施解决方案，尝试提交，得到错误答案或其他一些与接受不同的结果。
And then, you've made a few more changes, but it still didn't work.
然后，你做了一些更改，但它仍然没有用。
And then, you understand that your solution was wrong, completely from the start.
然后，您从一开始就明白您的解决方案是错误的。
And then you need a new solution, and you will have to implement it from scratch.
然后你需要一个新的解决方案，你必须从头开始实现它。
And that means that you've wasted all the time on implementation on the first wrong solution.
这意味着你在第一个错误的解决方案上一直浪费在实施上。
To avoid that, you should always prove your solution first.
为避免这种情况，您应该首先证明您的解决方案。
So after we've proved the safe move, we basically got our greedy solution.
因此，在我们证明安全行动之后，我们基本上得到了贪婪的解决方案。
Which works in combination with a certain algorithm in time n log n.
它与时间n log n中的某个算法结合使用。
Which is not only polynomial, but is very close to linear time, and works really fast in practice.
这不仅是多项式，而且非常接近线性时间，并且在实践中工作得非常快。
------------- 26 -------------
01长途徒步旅行
Hello.
你好。
In this lesson, you will learn an algorithm to determine which food items and in which amounts should you take with yourself on a really long hike so that to maximize their total energy value.
在本课程中，您将学习一种算法，以确定您应该在非常长的徒步旅行中自己采取哪些食物和量，以便最大化其总能量值。
So, you're planning a long hike.
所以，你计划长途跋涉。
It will take a few days or maybe a few weeks, but you don't know exactly how long will it take.
这将需要几天或几周，但你不知道它需要多长时间。
So, to be safe, you need to get enough food with you.
所以，为了安全起见，你需要随身携带足够的食物。
And you have a knapsack which can fit up to 15 kilograms of food in it.
你有一个背包，可以容纳15公斤的食物。
And you've already bought some cheese, some ham, some nuts, and maybe some other food items.
你已经买了一些奶酪，一些火腿，一些坚果，还有一些其他食品。
You want to fit them all in the knapsack, so as to maximize the amount of calories that you can get from them.
你想把它们全部放在背包中，以便最大化你可以从它们获得的卡路里量。
Of course you can cut the cheese.
当然你可以切奶酪。
You can cut the ham.
你可以切火腿。
You can select only some of the nuts.
您只能选择一些坚果。
And then fit all of that into your knapsack.
然后将所有这些都装进你的背包里。
To solve this maximization problem, we again need to first reformulate it in mathematical terms.
为了解决这个最大化问题，我们再次需要首先用数学术语重新表述它。
And then it becomes an instance of a classical fractional knapsack problem, which goes like this.
然后它成为经典的分数背包问题的一个例子，就像这样。
We have n items with weights w1 through wn and values v1 though vn.
我们有n个项目的权重为w1到wn，值为v1到vn。
And a bag of capacity big W.
还有一袋大容量的W.
And we want to maximize the total value of fractions of items that fit into this bag.
我们希望最大化适合此包的物品分数的总价值。
In this case, weights are also weights in the real life and values are the energy values of the food items that you've bought.
在这种情况下，权重也是现实生活中的权重，价值是您购买的食品的能量值。
So, here's an example, and we will denote by dollars the value of the item, and the weight just by numbers.
所以，这是一个例子，我们将用美元表示项目的价值，而权重仅用数字表示。
So, for example, the first item has value $20 and has weight 4, the second item has value $18 and weight 3, and the third item has value $14 and weight 2.
因此，例如，第一项的价值为20美元，重量为4，第二项的价值为18美元，重量为3，第三项的价值为14美元，重量为2。
And we have a knapsack of capacity 7.
我们有一个容量7的背包。
There are a few ways with which we can fill this knapsack.
我们有几种方法可以填充这个背包。
For example, of them is put the whole first item and the whole second item in the knapsack.
例如，他们将整个第一项和整个第二项放在背包中。
Then the total value is the sum of the values of the first item and the second, which is $38.
然后总值是第一项和第二项的值之和，即$ 38。
We can improve on that.
我们可以改进。
For example, take the whole first item, the whole third item, and only one third of the second item for a total value of $40.
例如，取整个第一个项目，整个第三个项目，以及第二个项目的三分之一，总价值为40美元。
We can do even better by taking the whole third item, the whole second item, and only half of the first item, and that will give us $42.
我们可以通过整个第三项，第二项，只有第一项的一半来做得更好，这将给我们42美元。
And actually it turns out that this is the optimal thing to do.
事实证明，这是最佳选择。
So now we want to create a greedy algorithm that will solve this maximization problem, and we need to get some greedy choice and make a safe move.
所以现在我们想要创建一个贪婪算法来解决这个最大化问题，我们需要得到一些贪婪的选择并做出安全的行动。
And to do that, we have to look at the value per unit of weight.
要做到这一点，我们必须考虑每单位重量的价值。
So, for example for the first item, value per unit of weight is $5, for the second item, it's $6 per unit, and for the third one it's $7 per unit.
因此，例如对于第一项，每单位重量的价值是5美元，对于第二项，每单位6美元，而对于第三项，每单位7美元。
So although the first item is most valuable, the third item has the maximum value per unit.
因此，虽然第一项是最有价值的，但第三项具有每单位的最大值。
And of course there is an intuition that we should probably fit first the items with the maximum value per unit.
当然，有一种直觉，我们应该首先适合每单位最大值的项目。
And really, the safe move is to first try to fit the item with the maximum value per unit.
实际上，安全的举措是首先尝试使每单位的最大值适合项目。
And there's a lemma that says that there always exists some optimal solution to our problem that uses as much as possible of an item with the maximum value per unit of weight.
并且有一个引理说，我们的问题始终存在一些最佳解决方案，它尽可能地使用具有每单位重量最大值的项目。
And what do we mean by as much as possible? Well, either use the whole item, if it fits into the knapsack, or, if the capacity of the knapsack is less than how much we have of this item, then just fill the whole knapsack only with this item.
我们的意思是什么？好吧，要么使用整个项目，如果它适合背包，或者，如果背包的容量小于我们对这个项目的容量，那么只需用这个项目填充整个背包。
Let's prove that this is really a safe move.
让我们证明这确实是一个安全的举措。
We will prove looking at this example.
我们将证明这个例子。
So, first let's suppose we have some optimal solution, and let's suppose that in this optimal solution, we don't use as much as possible of the best item with the highest value per unit of weight.
所以，首先让我们假设我们有一些最优的解决方案，让我们假设在这个最优解决方案中，我们不会尽可能多地使用每单位重量最高值的最佳项目。
Then take some item which we used in this solution and separate its usage into two parts, one part of the same size of how much we have of the best item, and the second part is everything else.
然后拿一些我们在这个解决方案中使用的项目，并将它的用法分成两部分，一部分是我们拥有最多项目的相同大小，第二部分是其他所有部分。
Then we can substitute the first part with the best item.
然后我们可以用最好的项目替换第一部分。
So, for example, in this case, we substitute half of the first item with second item.
因此，例如，在这种情况下，我们用第二项替换第一项的一半。
Of course, in this part, the total value will increase, because the value per unit of weight is better for the best item than for the item currently used.
当然，在这部分中，总价值会增加，因为每单位重量的价值对于最佳商品而言比对于当前使用的商品更好。
And in the general case, this will also work.
在一般情况下，这也将起作用。
So, either we will be able to replace some part of the item already used by the whole best item, or we can replace the whole item that is already used by some part of the best item.
因此，要么我们将能够替换整个最佳项目已经使用的项目的某些部分，要么我们可以替换最佳项目的某些部分已经使用的整个项目。
And in any case, if we can make such a substitution, of course the total value will increase, because the best item just has better value per unit of weight, so for each unit of weight, we will have more value.
在任何情况下，如果我们可以进行这样的替换，当然总价值会增加，因为最好的项目每单位重量只有更好的价值，所以对于每个重量单位，我们将有更多的价值。
So this gives us a greedy algorithm to solve our problem.
所以这给了我们一个贪婪的算法来解决我们的问题。
What we'll do is while knapsack is still not full, we will do a greedy choice.
我们要做的是背包仍未满，我们将做一个贪婪的选择。
We will choose the item number i which has the maximum value of vi over wi, which is the value per unit of weight.
我们将选择项目编号i，其最大值为vi而不是wi，即每单位重量的值。
And then if this item fits into knapsack fully, then take of all this item.
然后，如果这个项目完全适合背包，那么拿走所有这个项目。
Otherwise, if there is only few space left in the knapsack, take so much of this item as to fill the knapsack to the end.
否则，如果背包中只剩下很少的空间，那么就把这个项目当作填充背包到底。
And then in the end, we'll return the total value of the items that we took and how much did we take of each item.
然后最后，我们将返回我们拍摄的项目的总价值以及我们对每个项目的评价。
------------- 27 -------------
02分数背包实施分析和优化
Hi.
你好。
In this lesson you will learn how to implement the Greedy Algorithm for the Fractional Knapsack.
在本课中，您将学习如何实现分数背包的贪婪算法。
How to estimate its running time and how to improve its asymptotics.
如何估计其运行时间以及如何改进其渐近性。
Here is the description of the greedy algorithm from the previous lesson.
以下是上一课中贪婪算法的描述。
While knapsack is still not full, we select the best item left.
虽然背包仍然没有装满，但我们选择了最好的项目。
The one with the highest value per unit of weight.
每单位重量值最高的那个。
And either fit all of this item in the knapsack or if there is only few space left in the knapsack, cut this item and fit as much as you can in what's left in the knapsack, and then repeat this process until the knapsack is full.
并且要么在背包中放置所有这个项目，要么背包中只留下很少的空间，切割这个项目并尽可能多地放在背包里留下的东西，然后重复这个过程直到背包充满。
In the end return the total value of the items taken and the amounts taken.
最后返回所采用物品的总价值和所采取的金额。
We've proven that the selection of best item is a safe move.
我们已经证明，选择最佳项目是一个安全的举措。
Then after we've selected the best item what we've got left is a knapsack with a capacity which is less, but the problem is the same: you have some items and you have a knapsack of some capacity and you should fill it optimally so as to maximize the total value of the items that fit.
然后，在我们选择了最好的项目后，我们剩下的是一个容量较小的背包，但问题是相同的：你有一些物品，你有一些容量的背包，你应该最好地填充它以便最大化适合的项目的总价值。
So this greedy algorithm really works.
所以这个贪婪的算法确实有效。
Now let's implement it.
现在让我们来实现它。
Here we have a procedure called Knapsack.
这里我们有一个名为Knapsack的程序。
It starts with filling the array A with amounts of items taken with 0 and the total value we also initialize to 0 and then, as we said on the slide, we repeat for n times the following iterations.
它首先填充数组A，其中项目的数量为0，总值也初始化为0，然后，正如我们在幻灯片中所说，我们重复n次以下迭代。
If the knapsack is already full than in the variable W, we will have 0 because in the start we have in the variable W the total capacity of the knapsack, but each time we will put something in the knapsack, we will update W will decrease it by the amount of weight that we put already in.
如果背包已经满了比变量W，我们将有0因为在开始时我们在变量W中有背包的总容量，但每次我们将把东西放在背包里，我们会更新W会减少它是我们已经投入的重量。
And so in the end, when the knapsack is full, W will be 0.
最后，当背包已满时，W将为0。
If W became 0, it means that we should just return the total value and the amounts of the items that we took.
如果W变为0，则意味着我们应该返回总价值和我们采取的项目数量。
Otherwise we should select the best item.
否则我们应该选择最好的项目。
The best item is the item which is still left so, wi is more than 0 and out of such items, it's the item with the maximum value per weight, so the one which maximizes vi over wi.
最好的项目是仍然保留的项目，wi大于0且超出这些项目，它是具有每个权重的最大值的项目，因此是最大化vi而不是wi的项目。
When we've selected the i, we determine the amount which will it take, it is either the whole wi, the whole of this item if it fits in the knapsack.
当我们选择了i时，我们确定它将采取的数量，它是整个wi，如果它适合背包，则整个这个项目。
Otherwise, if the capacity of the knapsack is already less, then we just fill it up to the end.
否则，如果背包的容量已经减少了，那么我们就把它填满到最后。
So A is minimum of wi and big W.
所以A是最小的wi和大W.
After we select the amount, we just update all the variables.
选择金额后，我们只更新所有变量。
So we update wi by decreasing it by a, because we took already a of this item.
所以我们通过减少a来更新wi，因为我们已经使用了这个项目。
We're also increased the amount A of i corresponding to the item number i by the value A.
我们还通过值A增加了对应于项目编号i的i的量A.
And we'll also decrease the capacity left, because we just decrease it by A.
而且我们还会减少剩余的容量，因为我们只是将它减少了A.
By putting it A of item i.
把它作为项目i的A。
Also we increase value V by this formula: a multiplied by vi and divided by wi.
我们也通过这个公式增加值V：乘以vi并除以wi。
Why is that? Because we took A of item number i, we took A units and one unit brings us amount of value equal to vi over wi.
这是为什么？因为我们拿了项目编号i的A，我们拿了A个单位，一个单位给我们带来的价值等于vi而不是wi。
So if you take A units, the total value by these items, a multiplied by vi and divided by wi.
因此，如果你取A单位，这些项的总价值，乘以vi除以wi。
After we do n iterations, or maybe less, if the knapsack is full before we do all n iterations, we'll return the total value and the amounts in the array.
在我们进行n次迭代之后，或者更少，如果在我们进行所有n次迭代之前背包已满，我们将返回总值和数组中的数量。
Now the running time of this algorithm is Big-O of n squared.
现在这个算法的运行时间是n平方的Big-O。
Why is that? Well, first we have the inner selection of best item, which works in linear time.
这是为什么？好吧，首先我们有最佳项目的内部选择，它在线性时间内工作。
Because basically, we have to go through all the items to select the best one.
因为基本上，我们必须通过所有项目来选择最好的项目。
And we have the main loop, for loop, which is executed n times at most, maybe less.
我们有主循环，for循环，最多执行n次，可能更少。
So in each iteration we do some linear time computation and we do this at most n times.
所以在每次迭代中我们做一些线性时间计算，我们最多n次。
That means that the total running time is Big-O of n squared.
这意味着总运行时间是n平方的Big-O。
Now we can't improve on that because if we sort the items by decreasing value of vi over wi, then it will be easier to select the best item which is still left.
现在我们无法改进，因为如果我们通过减去vi的值来对项目进行排序，那么选择仍然剩下的最佳项目会更容易。
Let's look at this pseudo code.
我们来看看这个伪代码。
Let's assume that we've already sorted the input items, size that v1 over w1 is, more than or equal to v2 over w2 and that is greater, or equal to the fraction for the next item and up to vn over wn.
让我们假设我们已经对输入项进行了排序，v1超过w1的大小，大于或等于v2大于或等于w2，并且更大，或等于下一项的分数，直到vn大于wn。
And we can start with the same array of amounts and the same total value filled with zeroes.
我们可以从相同的数量数组开始，并使用零填充相同的总值。
But then we make a for loop for i going from 1 to n.
但是接着我们从1到n进行for循环。
And on each iteration i will be the best unit which is still left.
在每次迭代中，我将是仍然离开的最佳单位。
So on the start of the iteration we check whether we still have some capacity in the knapsack.
因此，在迭代开始时，我们检查我们是否仍然在背包中有一些容量。
If it is already filled we just return the answer.
如果它已经填满，我们只返回答案。
Otherwise we know that i is the best item because we didn't consider it previously and it is the item with the maximum value per unit out of those which we didn't consider before.
否则我们知道我是最好的项目，因为我们以前没有考虑过这个项目，而且它是我们之前没有考虑过的每单位最大价值的项目。
So we determine the amount of this item with the same formula and we update the weights, the amounts, the capacity, and the total value in the same way as we did in the previous pseudocode.
因此，我们使用相同的公式确定此项目的数量，并以与上一个伪代码相同的方式更新权重，数量，容量和总值。
The only change is that we change the order in which we consider the items.
唯一的变化是我们改变了我们考虑项目的顺序。
And this allows us to make each iteration in constant time instead of linear time.
这使我们能够以恒定时间而不是线性时间进行每次迭代。
So, this new algorithm now works in linear time, because it has at most n iterations, and each iteration works at most in constant time.
因此，这种新算法现在可以在线性时间内工作，因为它最多只有n次迭代，并且每次迭代最多可以在恒定时间内工作。
So, if we apply first some sorting algorithm to sort items by decreasing value of vi over wi.
因此，如果我们首先应用一些排序算法来通过减少vi的值来对项目进行排序。
And then apply this new knapsack procedure.
然后应用这个新的背包程序。
Total run time will be n log n, because sorting will work in n log n.
总运行时间将为n log n，因为排序将在n log n中起作用。
And the knapsack itself will work in linear time.
背包本身将在线性时间内工作。
------------- 28 -------------
03评论贪心算法
Hi, in this lesson, we will review what we saw in this module about greedy algorithms and specify what is common and important to all greedy algorithms.
嗨，在本课中，我们将回顾一下我们在本单元中看到的关于贪婪算法的内容，并指出所有贪婪算法的常见和重要之处。
The main ingredients of any greedy algorithm are greedy choice and reduction to a subproblem.
任何贪婪算法的主要成分是贪婪的选择和减少到子问题。
You have to prove that your greedy choice is a safe move.
你必须证明你贪婪的选择是一个安全的举动。
And also, you have to check that the problem that is left after your safe move is really a subproblem.
而且，你必须检查安全移动后留下的问题是否真的是一个子问题。
That is, a problem of the same kind but with fewer parameters.
也就是说，同一种问题但参数较少的问题。
After you have both, you have a greedy algorithm.
拥有两者后，你有一个贪心的算法。
Then, you need to estimate its running time and check that it's good enough for you.
然后，您需要估计其运行时间并检查它是否足够好。
Safe moves in different problems are different.
不同问题的安全行动是不同的。
Basically, you have to invent something each time you have a new problem.
基本上，每次遇到新问题时都必须发明一些东西。
In the first problem it was, select the maximum digit and put it first.
在第一个问题中，选择最大数字并将其放在第一位。
In the last problem it was select the item with the maximum total value per weight.
在最后一个问题中，选择具有每重量最大总值的项目。
And you see that in every safe move, there's something like maximum, or minimum, or first, or leftmost, or rightmost.
而且你会发现，在每一个安全行动中，都会有最大值或最小值，或者首先，最左边或最右边的东西。
So, always safe move is greedy, but not all greedy moves are safe.
所以，总是安全的举动是贪婪的，但不是所有的贪婪举动都是安全的。
So, you really have to prove every time that the move that you invented is really safe.
所以，你必须每次证明你发明的这一举动是非常安全的。
Also, you can notice that sometimes we can optimize our initial greedy algorithm if we sort our object somehow.
此外，您可以注意到，如果我们以某种方式对对象进行排序，有时我们可以优化我们的初始贪心算法。
So, you can maybe try to solve problem, assuming that everything is sorted in some convenient order.
因此，您可以尝试解决问题，假设所有内容都按照一些方便的顺序排序。
And if you see that, because of that, your greedy algorithm can be implemented asymptotically faster, then you can just apply sorting first and then your greedy algorithm.
如果你看到这一点，那么，你的贪婪算法可以渐进地实现，然后你可以先应用排序然后再应用你的贪心算法。
The general strategy is when I have a problem, you can try to come up with some greedy choices, and then for some of them, you'll be able to prove that they're really safe moves.
一般策略是当我遇到问题时，你可以尝试提出一些贪婪的选择，然后对于其中一些，你将能够证明它们是非常安全的动作。
And if you've proven that this is a safe move, then you've reduced your problem to something.
如果你已经证明这是一个安全的举动，那么你已经将问题减少了。
And then you have to check that this something is a subproblem.
然后你必须检查这个东西是一个子问题。
That is, the problem about the same thing, optimizing the same thing with the same restrictions.
也就是说，关于同样的事情的问题，用相同的限制优化同样的事情。
And then, this is a subproblem.
然后，这是一个子问题。
And then you can solve it in the same way that you solved your initial problem.
然后你可以用解决初始问题的方式来解决它。
And you have this loop from problem to subproblem and back to the problem, always reducing it by the number of parameters.
你有从问题到子问题的循环，然后回到问题，总是通过参数的数量减少它。
And in the end of this loop, you will have a problem so simple that you can solve it right away for one object or zero objects.
在这个循环的最后，你会遇到一个简单的问题，你可以立即解决一个对象或零对象。
And then you have your greedy algorithm.
然后你有你的贪心算法。
------------- 29 -------------
01介绍
Hi, I'm Neil Rhodes.
嗨，我是Neil Rhodes。
Welcome to the divide and conquer module.
欢迎来到分而治之的模块。
In the last module, you learned about how to use greedy algorithms to solve particular classes of problems.
在最后一个模块中，您学习了如何使用贪婪算法来解决特定类型的问题。
In this module you'll learn about ways of solving problems using divide and conquer algorithms.
在本单元中，您将学习使用分而治之算法解决问题的方法。
The term divide and conquer is quite old, and when applied to war, suggests that it's easier to defeat several smaller groups of opponents than trying to defeat one large group.
“分而治之”这个术语相当古老，当应用于战争时，它表明，与试图击败一个大集团相比，击败几个较小的对手组更容易。
In a similar fashion, divide and conquer algorithms take advantage of breaking a problem down into one or more subproblems that can then be solved independently.
以类似的方式，分而治之的算法利用将问题分解为一个或多个子问题，然后可以独立解决。
Just as not all problems can be solved with a greedy algorithm, not all problems can be solved using divide and conquer.
正如并非所有问题都可以通过贪婪算法解决，并非所有问题都可以通过分而治之来解决。
Instead, these are both techniques that are part of a toolbox of strategies to solve problems.
相反，这些都是技术，是解决问题的策略工具箱的一部分。
As you're designing an algorithm, you'll need to consider whether or not a greedy algorithm might work.
在设计算法时，您需要考虑贪婪算法是否可行。
If not, would a divide and conquer algorithm work? Let's look at the general structure of a divide and conquer algorithm.
如果没有，分而治之的算法会起作用吗？让我们看一下分而治之算法的一般结构。
Here, we have a problem to be solved represented abstractly as a blue rectangle.
在这里，我们有一个要解决的问题，抽象地表示为蓝色矩形。
We break the problem down into a set of non-overlapping subproblems.
我们将问题分解为一组非重叠的子问题。
Represented here, by colored rectangles.
这里用彩色矩形表示。
It's important that the subproblems be of the same type as the original.
子问题与原始问题的类型非常重要。
For example, here's a way to break down the original rectangle problem into a set of subproblems that are not of the same type.
例如，这是一种将原始矩形问题分解为一组不同类型的子问题的方法。
These subproblems are triangles.
这些子问题是三角形。
Thus this does not represent the divide and conquer algorithm.
因此，这并不代表分而治之的算法。
In this case, we've broken down the original rectangle problem into a set of subproblems that are themselves rectangles.
在这种情况下，我们将原始矩形问题分解为一组本身为矩形的子问题。
The difficulty is that these subproblems overlap with one another.
困难在于这些子问题彼此重叠。
Thus it too does not represent the divide and conquer algorithm.
因此它也不代表分而治之的算法。
We return now to breaking down our problem into a set of non-overlapping subproblems of the same original type.
我们现在返回将我们的问题分解为一组相同原始类型的非重叠子问题。
We break it apart, then we go ahead and solve each subproblem independently.
我们将它分开，然后我们继续独立解决每个子问题。
We solve the first problem, represented by a check mark.
我们解决了第一个问题，用复选标记表示。
We then continue solving each problem, in turn.
然后我们继续解决每个问题。
Once we've successfully solved each of the subproblems, we combine the results into a solution to the original problem.
一旦我们成功解决了每个子问题，我们将结果组合成原始问题的解决方案。
One question that comes up, how do we solve each subproblem? Since each subproblem is of the same type as the original, we can recursively solve the subproblem using the same divide and conquer strategy.
提出一个问题，我们如何解决每个子问题？由于每个子问题与原始子问题的类型相同，我们可以使用相同的分而治之策略递归地解决子问题。
Thus, divide and conquer algorithms naturally lead to a recursive solution.
因此，分而治之的算法自然会导致递归解决方案。
In practice, while you can program a divide and conquer algorithm recursively, it's not uncommon to rewrite the recursive program into an iterative one.
实际上，虽然您可以递归地编写分治算法，但将递归程序重写为迭代程序并不罕见。
This is often done both because some programmers aren't as comfortable with recursion as they are with iteration, as well as because of the additional space that a recursive implementation may take in terms of additional stack space.
这通常都是因为一些程序员不像迭代那样对递归感到满意，也因为递归实现可能在额外的堆栈空间方面占用额外的空间。
This can be language and implementation dependent.
这可能取决于语言和实现。
In summary, the divide and conquer algorithm consists of one: breaking the problem into non-overlapping subproblems of the same type.
总之，分而治之算法包括一个：将问题分解为相同类型的非重叠子问题。
Two: recursively solving those subproblems.
二：递归解决这些子问题。
And three: combining the results.
三：结合结果。
In the next video, we'll see an extremely simple example of divide and conquer.
在下一个视频中，我们将看到一个非常简单的分而治之的例子。
------------- 30 -------------
02线性搜索
We're going to start our divide and conquer algorithms with what might be considered a degenerate form of divide and conquer: Searching in an unsorted array using linear search.
我们将开始分裂并用可能被认为是分裂和征服的退化形式征服算法：使用线性搜索在未排序的数组中搜索。
Here's an example of an array.
这是一个数组的例子。
To find a particular element of the array, we look at the first element, if it's not there, we look at the second element.
为了找到数组的特定元素，我们查看第一个元素，如果它不存在，我们将查看第二个元素。
We continue until we either find the element we're interested in, or until we reach the end of the array.
我们继续，直到找到我们感兴趣的元素，或者直到我们到达数组的末尾。
This same type of search is also used to free elements that are stored in a linked list.
这种类型的搜索也用于释放存储在链表中的元素。
Let me describe a real-life use of linear search.
让我描述线性搜索的实际使用。
Twenty years ago I did consulting for a company developing software for one the first hand-held computers, the Apple Newton.
二十年前，我为一家为第一台手持电脑Apple Newton开发软件的公司提供咨询服务。
The application translated words between any two of the languages: English, French, Italian, German, or Spanish.
该应用程序翻译了任何两种语言之间的文字：英语，法语，意大利语，德语或西班牙语。
Its data was stored in five parallel arrays.
它的数据存储在五个并行数组中。
So for example, car was in English at the second position.
因此，例如，汽车在第二位置是英语。
In Spanish, car is auto, so the second position of the Spanish array contained auto.
在西班牙语中，car是auto，所以西班牙语数组的第二个位置包含auto。
The program would take the user's input word along with from and to languages.
该程序将使用用户的输入词以及语言和语言。
Then it would search through the corresponding from array, English for example with trying to translate car from English to Spanish.
然后它将搜索相应的数组，例如英语，试图将汽车从英语翻译成西班牙语。
If it found a match, it returned the element at the same index location and target language.
如果找到匹配项，则返回相同索引位置和目标语言的元素。
With a small dictionary of three words, as in this example, this linear search is quick.
使用三个单词的小字典，如本例所示，这种线性搜索很快。
However, I was brought in as a consultant to speed up the application.
但是，我是作为顾问加入应用程序的。
When users clicked on the translate button, it'd take seven to ten seconds to retrieve the translated word, an eternity as far as the user was concerned.
当用户点击翻译按钮时，需要七到十秒的时间来检索翻译的单词，就用户而言是永恒的。
There were about 50,000 words in the dictionary, so on average it took 25,000 word checks in order to find a match.
字典中大约有50,000个单词，因此平均需要25,000个单词检查才能找到匹配项。
The next video, I'll show you how we sped up this application using binary search.
下一个视频，我将向您展示我们如何使用二进制搜索加速此应用程序。
The problem statement for linear search is as follows: given an unsorted array with n elements in it and a key k, find an index, i of the array element that's equal to k.
线性搜索的问题陈述如下：给定一个带有n个元素的未排序数组和一个密钥k，找到一个等于k的数组元素的索引i。
If no element array is equal to k, the output should be NOT_FOUND.
如果没有元素数组等于k，则输出应为NOT_FOUND。
Note that we say an index rather than the index, to account for the fact that there may be duplicates in the array.
请注意，我们说索引而不是索引，以说明数组中可能存在重复的事实。
This might seem pedantic, but it's important to be as careful as possible in specifying our problem statement.
这可能看起来很迂腐，但在指定我们的问题陈述时要尽可能小心谨慎。
The well known solution to this problem is a linear search.
该问题的众所周知的解决方案是线性搜索。
Iterate through the array until you find the chosen element.
遍历数组直到找到所选元素。
If you reach the end of the array and haven't yet found the element, return NOT_FOUND.
如果到达数组的末尾但尚未找到该元素，则返回NOT_FOUND。
We can construct a divide and conquer recursive algorithm to solve this problem.
我们可以构造一个分而治之的递归算法来解决这个问题。
Our recursive function will take four parameters: A, the array of values; low, the lower bound of the array in which to search; hgh, the upper bound of the array in which to search; and k, the key for which to search.
我们的递归函数将采用四个参数：A，值数组; low，要搜索的数组的下限; hgh，要搜索的数组的上限; 和k，搜索的关键。
It will return either: an index in the range low to high, if it finds a matching value; or NOT_FOUND, if it finds no such match.
如果找到匹配值，它将返回：从低到高范围内的索引; 或NOT_FOUND，如果找不到这样的匹配。
As with all recursive solutions, we'll need to accurately handle the base case.
与所有递归解决方案一样，我们需要准确处理基本情况。
In particular, base cases for this problem will be either: be given an empty array, or finding a match on the first element.
特别是，此问题的基本情况将是：给出一个空数组，或在第一个元素上找到匹配项。
The subproblem is to search through the sub array constructed by skipping the first element.
子问题是通过跳过第一个元素来搜索构造的子数组。
We'll recursively search through that smaller sub array, and then just return the result of the recursive search.
我们将递归搜索那个较小的子数组，然后只返回递归搜索的结果。
Although this is a recursive routine that breaks the problem into smaller problems, some would argue that this shouldn't be called divide and conquer.
虽然这是一个将问题分解为较小问题的递归例程，但有些人会认为这不应该被称为分而治之。
They claim that a divide and conquer algorithm should divide the problem into a smaller subproblem, where the smaller subproblem is some constant fraction of the original problem.
他们声称分而治之算法应该将问题分成一个较小的子问题，其中较小的子问题是原始问题的一些不变部分。
In this case the su-problem isn't 50%, or 80%, or even 95% of the original problem size.
在这种情况下，su问题不是原始问题大小的50％，或80％，或甚至95％。
Instead, it's just one smaller than the original problem size.
相反，它只比原始问题大小小一个。
I don't know, maybe we should call this algorithm subtract and conquer rather than divide and conquer.
我不知道，也许我们应该把这个算法称为减法和征服而不是分而治之。
In order to examine the runtime of our recursive algorithm it's often useful to define the time that the algorithm takes in the form of a recurrence relation.
为了检查递归算法的运行时间，定义算法采用递归关系形式的时间通常很有用。
A recurrence relation defines a sequence of values in terms of a recursive formula.
递归关系根据递归公式定义值序列。
The example here shows the recursive definition of the values in the Fibonacci sequence.
此处的示例显示了Fibonacci序列中值的递归定义。
You can see that we defined the value for the n'th Fibonacci as the sum of the preceding two values.
您可以看到我们将第n个Fibonacci的值定义为前两个值的总和。
As with any recursive definition, we need one or more base cases.
与任何递归定义一样，我们需要一个或多个基本情况。
Here, we define base cases when evaluating F(0) and F(1).
在这里，我们在评估F（0）和F（1）时定义基本情况。
From this recursive definition, we've defined values for evaluating F(n) for any non-negative integer, n.
从这个递归定义中，我们定义了用于评估任何非负整数n的F（n）的值。
The sequence starts with 0, 1, 1, 2, 3, 5, 8, and continues on.
序列以0,1,1,2,3,5,8开始，并继续。
When we're doing run-time analysis for divide and conquer algorithms, we usually define a recurrence relation for T(n).
当我们对分而治之算法进行运行时分析时，我们通常会定义T（n）的递归关系。
where T stands for the worst time taken for the algorithm, and n is the size of the problem.
其中T代表算法所用的最差时间，n是问题的大小。
For this algorithm, the worst-case time is when an element isn't found because we must check every element of the array.
对于此算法，最坏情况时间是找不到元素，因为我们必须检查数组的每个元素。
In this case we have a recursion for a problem of size n which consists of a subproblem of size n minus one plus a constant amount of work.
在这种情况下，我们对大小为n的问题进行递归，该问题由大小为n的子问题减去1加上恒定的工作量组成。
The constant amount of work includes checking high versus low, checking A at low equals key, preparing the parameters for the recursive call, and then returning the result of that call.
恒定的工作量包括检查高与低，检查A等于低等于密钥，准备递归调用的参数，然后返回该调用的结果。
Thus the recurrence is T(n) equals T(n-1) plus c, where c is some constant.
因此，重现是T（n）等于T（n-1）加c，其中c是某个常数。
The base case of the recursion is in an empty array, there's a constant amount of work: checking high less than low and then returning NOT_FOUND.
递归的基本情况是一个空数组，有一个恒定的工作量：检查高于低值然后返回NOT_FOUND。
Thus T(0) equals c.
因此T（0）等于c。
Let's look at a recursion tree in order to determine how much total time the algorithm takes.
让我们看一个递归树，以确定算法花费的总时间。
As is normal, we're looking at worst-case runtime, which will occur when no matching element is found.
正常情况下，我们正在查看最坏情况运行时，这将在找不到匹配元素时发生。
In a recursion tree, we show the problem along with the size of the problem.
在递归树中，我们显示问题以及问题的大小。
We see that we have an original problem of size n which then generates a subproblem of size n-1, and so on all the way down to a subproblem of size zero: an empty array.
我们看到我们有一个大小为n的原始问题，然后生成一个大小为n-1的子问题，依此类推到一个大小为零的子问题：一个空数组。
The work column shows the amount of work that is done at each level.
工作栏显示每个级别的工作量。
We have a constant amount of work at each level which we represent by c, a constant.
我们在每个级别都有不变的工作量，我们用c代表一个常量。
Alternatively, we could have represented this constant amount of work with big theta of one.
或者，我们可以用一个大的θ代表这个不变的工作量。
The total work is just the sum of the work done at each level that's a summation from zero to n of a constant c.
总工作量只是每个级别所做工作的总和，它是从零到n的常数c的总和。
Which is n plus one times c, or just big theta of n.
这是n加c的一倍，或者只是n的大θ。
This analysis seems overly complicated for such a simple result.
对于如此简单的结果，这种分析似乎过于复杂。
We already know that searching through n elements of the array will take big theta of n time.
我们已经知道，搜索数组中的n个元素将占用n次。
However, this method of recurrence analysis will become more useful as we analyze more complicated divide and conquer algorithms.
然而，当我们分析更复杂的分治算法时，这种递归分析方法将变得更有用。
Many times a recursive algorithm is translated into an iterative one.
很多时候，递归算法被转换为迭代算法。
Here we've done that for the linear search.
在这里，我们已经完成了线性搜索。
We search through the elements of array A from index low to index high.
我们搜索数组A的元素，从索引低到索引高。
If we find a match, we return the associated index.
如果我们找到匹配项，则返回关联的索引。
If not, we return NOT_FOUND.
如果没有，我们返回NOT_FOUND。
To summarize, what we've done is one: created a recursive solution; two: defined a corresponding recurrence relation, T; three: solved T of n to determine the worst-case runtime; and four: created an iterative solution from the recursive one.
总而言之，我们所做的就是：创建一个递归解决方案; 二：定义了相应的递归关系，T; 三：求解n的T来确定最坏情况的运行时间; 和四：从递归的解决方案中创建迭代解决方案。
What you've seen in this video, then, is an example of a trivial use of our divide and conquer technique in order to do a linear search.
那么，你在这个视频中看到的是一个简单使用我们的分而治之技术来进行线性搜索的例子。
In our next video we'll look at a non-trivial use of the divide an conquer technique for searching in a sorted array: the well known binary search.
在我们的下一个视频中，我们将看到一个非常重要的用于在一个有序数组中进行搜索的征服技术：众所周知的二进制搜索。
------------- 31 -------------
03二进制搜索
Hi, so let's talk now about binary search.
嗨，现在让我们谈谈二进制搜索。
A dictionary is a good example of a ordered list.
字典是有序列表的一个很好的例子。
Okay, basically where every word is in order.
好的，基本上每个单词都是有序的。
And that makes finding words much easier.
这使得查找单词变得更容易。
You can imagine how difficult it would be to search a dictionary if the order of the words was random.
你可以想象，如果单词的顺序是随机的，搜索字典是多么困难。
You'd have to just search through every single page, and in fact, every word on every page.
你必须只搜索每一页，事实上，每页上的每个单词。
It'd take quite a long time.
这需要很长时间。
So let's look at the problem statement for searching in a sorted array.
那么让我们看一下在排序数组中搜索的问题陈述。
So what we have coming in is, A, an array, along with a low and upper bound that specify the bounds within the array in which to search.
所以我们得到的是A，一个数组，以及一个低限和上限，指定数组中要搜索的范围。
What's important about the array is that it's in sorted order.
这个数组最重要的是它按排序顺序排列。
What we mean by that is if we look at any index i at an element.
我们的意思是，如果我们看一个元素的任何索引i。
And then the next element, that this first element is no more than the next element.
然后是下一个元素，即第一个元素不过是下一个元素。
We don't say less than because we want to allow for arrays that have repeated elements.
我们不要说因为我们想要允许具有重复元素的数组。
So officially this is called a monotonic non-decreasing array.
所以正式这被称为单调非递减阵列。
The other input is the key to look for.
另一个输入是寻找的关键。
The output for this is an index such that the element at that index in the array is equal to the key.
此输出是一个索引，使得数组中该索引处的元素等于键。
We say an element and not the element just as we did in linear search.
我们说的是元素而不是元素，就像我们在线性搜索中所做的那样。
because of the fact that there may be more than one element-- more than one element that matches because there may be duplicates in the array.
因为可能存在多个元素 - 多个元素匹配，因为数组中可能存在重复。
If we don't have a match, instead of returning NOT_FOUND as we did in the linear search case, we're going to actually return somewhat more useful information, which is where in the array would you actually insert the element if you wanted to insert it? Or where would it have been, if it were there? So what we're going to return is the greatest index, such that A sub i is less than k.
如果我们没有匹配，而不是像在线性搜索情况中那样返回NOT_FOUND，我们将实际返回一些更有用的信息，如果你想要在数组中实际插入元素的位置插入？或者它会在哪里，如果它在那里？所以我们要返回的是最大的指数，这样A sub i小于k。
That is, if the key is not in the array, we're returning an index such that if you look at the element at that index, it's less than the key but the next element is greater than the key.
也就是说，如果键不在数组中，我们将返回一个索引，如果你查看该索引处的元素，它会小于键，但下一个元素大于键。
And we do have to take account of the fact that what if every element in the array is greater than the key? In that case, we're going to go ahead and return low- 1.
而且我们必须考虑到如果数组中的每个元素都大于键那么该怎么办？在那种情况下，我们将继续前进并返回低位1。
So look at an example.
那么看一个例子。
We've got this array with 7 elements in it, and the element 20 is repeated in it.
我们有一个包含7个元素的数组，元素20在其中重复。
So if we search in this array for 2, we want to go ahead and return 0, saying that every element in the array is larger than this.
因此，如果我们在这个数组中搜索2，我们希望继续返回0，表示数组中的每个元素都大于此值。
If on the other hand, we look for 3, we're going to return 1.
另一方面，如果我们寻找3，我们将返回1。
If we look for 4, we're also going to be returning 1.
如果我们寻找4，我们也将返回1。
which really signifies between 1 and 2.
这实际上意味着1和2之间。
That is, it's bigger than 3 but it's less than 5.
也就是说，它大于3但不到5。
If we search for 20, we return 4.
如果我们搜索20，我们返回4。
Or we might also return 5.
或者我们也可能会返回5。
Either one of those is valid because 20 is present at each of those indexes.
其中任何一个都是有效的，因为每个索引都有20个。
And if we search for 60, we'll return 7.
如果我们搜索60，我们将返回7。
But if we search for 70, we'll also return 7.
但如果我们搜索70，我们也将返回7。
So let's look at our implementation of BinarySearch.
那么让我们看一下BinarySearch的实现。
So we're going to write a recursive routine, taking in A, low, high and key, just as we specified in the problem statement.
因此，我们将编写一个递归例程，接受A，low，high和key，就像我们在问题陈述中指定的那样。
First our base case.
首先我们的基础案例。
If we have an empty array, that is if high is less than low, so no elements, then we're going to return low-1.
如果我们有一个空数组，那就是如果high低于low，那么没有元素，那么我们将返回low-1。
Otherwise, we're going to calculate the midpoint.
否则，我们将计算中点。
So we want something halfway between low and high.
所以我们想要从低到高之间的中间位置。
So what we're going to do is figure the width, which is high- low, cut it in half, so divide by 2, and then add that to low.
所以我们要做的是计算宽度，即高 - 低，将其减半，然后除以2，然后将其加到低位。
That might not be an integer because of the fact that high- low divided by 2 may give us a fractional portion, so we're going to take the floor of that.
这可能不是一个整数，因为高 - 低除以2可能会给我们一个小数部分，所以我们将采取行动。
For example, in the previous case, we had 1 to 7, it'll be 7- 1 is 6, divided by 2 is 3 + our low is 1 is 4, so the midpoint would be 4.
例如，在前一种情况下，我们有1到7，它将是7-1是6，除以2是3 +我们的低是1是4，所以中点将是4。
We'll see an example of this shortly.
我们很快就会看到一个例子。
And now we check and see is the element at that midpoint equal to our key.
现在我们检查并看到该中点的元素等于我们的键。
If so, we're done, we return it.
如果是这样，我们已经完成了，我们将其归还。
If not, the good news is of course, we don't have to check all the other elements, we've ruled out half of them.
如果没有，好消息当然是，我们不必检查所有其他元素，我们已经排除了其中一半。
So if the key is less than the midpoint element, then all the upper ones we can ignore.
因此，如果键小于中点元素，那么我们可以忽略所有上层元素。
So we're going to go ahead and now return the BinarySearch in A from low to mid- 1, completely ignoring all the stuff over here.
因此我们将继续前进，现在将A中的BinarySearch从低到中1返回，完全忽略了这里的所有内容。
Otherwise, the key is greater than the midpoint, and again, we can throw away the lower stuff and go from midpoint + 1, all the way to high.
否则，键值大于中点，再次，我们可以扔掉较低的东西，从中点+ 1，一直到高点。
Let's look at an example.
我们来看一个例子。
So let's say we're searching for the key 50 in this array with 11 elements.
因此，假设我们正在使用11个元素搜索此数组中的键50。
So we'll do a binary search on this array, from 1 to 11, looking for 50.
所以我们将对这个数组进行二进制搜索，从1到11，寻找50。
Low is 1, high is 11.
低是1，高是11。
We'll calculate the midpoint, the midpoint will be 11- 1 is 10, divided by 2 is 5, add that to 1, the midpoint is 6.
我们将计算中点，中点将是11-1是10，除以2是5，将其加到1，中点是6。
And now we check and see is the midpoint element equal to 50? Well, no.
现在我们检查并看到中点元素等于50？好吧，不。
The midpoint element is 15 and the element we are looking for, the key we're looking for, is 50.
中点元素是15，我们正在寻找的元素，我们正在寻找的关键是50。
So we're going to go ahead and ignore the lower half of the array and now call binary search again, with the low equal to 7, so one more than the midpoint.
因此，我们将继续忽略数组的下半部分，现在再次调用二进制搜索，低等于7，因此比中点多一个。
So now we've got a smaller version of the problem.
所以现在我们有一个较小版本的问题。
We're looking for 50 within the elements 7 to 11, we'll calculate the midpoint.
我们在元素7到11中寻找50，我们将计算中点。
11- 7 is 4 divided by 2 is 2, so we'll add that to 7 to get a midpoint of 9.
11- 7是4除以2是2，所以我们将其加到7得到9的中点。
We check, is the element at index 9 equal to our key? The element at index 9 is 20, our key is 50, they're not equal.
我们检查，索引9处的元素是否等于我们的键？索引9处的元素是20，我们的键是50，它们不相等。
However, 50 is greater than 20, so we're going to go ahead and make a new recursive call with midpoint + 1, which is 10.
但是，50大于20，所以我们将继续使用中点+ 1（即10）进行新的递归调用。
So, again, we do our binary search from 10 to 11.
所以，我们再次从10到11进行二进制搜索。
We calculate the midpoint.
我们计算中点。
High- low, 11- 10 is 1, divided by 2 is one-half + 10 is 10 and a half, we take the floor of that, we get 10 and a half, so our midpoint is 10 and a half.
高 - 低，11 - 10是1，除以2是一半+ 10是10，我们采取的是，我们得到10点半，所以我们的中点是10点半。
I'm sorry, our midpoint is 10.
对不起，我们的中点是10点。
And now we check.
现在我们检查一下。
Is the value at element 10 equal to our key? Well the value at element 10 is 50, our key is 50 so yes.
元素10的值是否等于我们的键？元素10的值是50，我们的关键是50，所以是的。
We're going to go ahead and return that midpoint which is 10.
我们将继续前进并返回10点的中点。
In summary then, what we've done is broken our problem into non-overlapping subproblems of the same type.
总而言之，我们所做的是将我们的问题分解为相同类型的非重叠子问题。
We've recursively solved the subproblems.
我们递归地解决了子问题。
And then we're going to combine the results of those subproblems.
然后我们将结合这些子问题的结果。
We broke the problem into a problem of size half (slightly less than half).
我们将问题分解为大小一半（略小于一半）的问题。
We recursively solved that single subproblem and then we combined the result very simply just by returning the result.
我们递归地解决了单个子问题，然后我们通过返回结果非常简单地组合结果。
In the next video, we're going to go ahead and look at the runtime for binary search, along with an iterative version.
在下一个视频中，我们将继续讨论二进制搜索的运行时以及迭代版本。
And we'll get back to actually discussing that problem that I discussed with the dictionary translation problem.
我们将回到实际讨论我讨论的字典翻译问题。
We'll see you shortly.
我们很快就会见到你。
------------- 32 -------------
04二进制搜索运行时
Hi, in this video we're going to be looking at the run time of BinarySearch along with looking at an iterative version of it.
嗨，在这个视频中，我们将查看BinarySearch的运行时间以及查看它的迭代版本。
So here's our BinarySearch algorithm again.
所以这是我们的BinarySearch算法。
We look in the middle, if it's not found, then we either look in the lower half or the upper half.
我们看中间，如果没有找到，那么我们要么看下半部分还是上半部分。
So whats our recurrence relation for the worst-case runtime? Well, the worst case is if we don't find an element.
那么最坏情况运行时的递归关系是什么？好吧，最糟糕的情况是如果我们找不到元素。
So were going to look at T(n) Is equal to T of roughly n over 2 + c.
所以要看T（n）等于大约n超过2 + c的T.
We have a floor there of n over 2 because if n is odd, let's say there are five elements, then the question is: how big is the problem size on the next call.
我们有一个n超过2的楼层，因为如果n是奇数，假设有五个元素，那么问题是：下一次调用时问题大小有多大。
So if we have five elements we're going to either end up looking in the upper half of the array.
因此，如果我们有五个元素，我们将最终查看数组的上半部分。
Those two elements or the lower half of the array, those two elements because we skipped the midpoint.
那两个元素或数组的下半部分，那两个元素因为我们跳过了中点。
We already checked them.
我们已经检查了它们。
Plus some constant amount of work to add together, to calculate the midpoint.
加上一些不断增加的工作量来计算中点。
As well as checking the midpoint against the key.
以及根据钥匙检查中点。
And then our base case is when we have an empty array.
然后我们的基本情况是我们有一个空数组。
And that's just a constant amount of time to check.
这只是一个不变的时间来检查。
So what's the runtime look like? We got our original size n, and we're going to break it down, n over 2, n over 4.
那么运行时是什么样的？我们得到了我们原来的大小n，我们将打破它，n超过2，n超过4。
All the way down.
一直往下。
How many of these problems are there.
有多少这些问题。
Well, if we're cutting something in two over and over again.
好吧，如果我们一次又一次地切两件事。
It's going to take log base two such iterations until we get down to 1.
它将采用log base两次这样的迭代，直到我们降到1。
So the total here, is actually log base two of n + 1.
所以这里的总数实际上是n + 1的log base 2。
The amount of work we're doing is c.
我们正在做的工作量是c。
So at each level, we're doing c work.
所以在每个级别，我们都在做c工作。
So the total amount of work if we sum it, is just the sum from i=0 to log base 2 of n of c.
因此，如果我们总结它的总工作量，只是从i = 0到c的n的log 2的总和。
That is just log base 2 of n + 1, that is log base 2 of n, that quantity, plus one times c.
这只是n + 1的对数基数2，即n的对数基数2，该数量加c的一倍。
And that is just theta of log based two of n, but really what we'd normally say is theta of log n, because the base doesn't matter.
这只是基于n的两个基数的log，但实际上我们通常所说的是log n的theta，因为基数并不重要。
That's just a constant multiplicative factor.
这只是一个不变的乘法因素。
All right, what's the iterative version look like.
好吧，迭代版本是什么样的。
The iterative version has the same parameters low, high, and key.
迭代版本具有相同的参数low，high和key。
And we have a while loop that goes through similar to the base case so in the base case of the recursive version we were stopping if high is less than low.
我们有一个类似于基本情况的while循环，因此在递归版本的基本情况下，如果high低于low，我们就会停止。
Here, we have a while loop where the while loop stops if high is less than low.
在这里，我们有一个while循环，如果high低于low，while循环停止。
We calculate the midpoint and then again check the key.
我们计算中点，然后再次检查密钥。
If it matches the element at the midpoint we return the midpoint.
如果它与中点处的元素匹配，则返回中点。
Otherwise, if the key is less than the element, we know we're in the first half of the array and so instead of making a new recursive call like we did in the recursive version we have the original array.
否则，如果键小于元素，我们知道我们在数组的前半部分，因此不像我们在递归版本中那样进行新的递归调用，而是使用原始数组。
And we want to look at the first half of it so we're going to change the value of high and that will be mid minus one because we already checked mid.
我们想看看它的前半部分，所以我们要改变高值，这将是中间减去一，因为我们已经检查了中期。
Otherwise, we want to look in the upper half of the array so we move low up.
否则，我们想要查看数组的上半部分，以便我们向上移动。
If we reach the end of the while loop.
如果我们到达while循环的末尾。
That is if we drop out of the while loop because high is less than low.
那就是如果我们退出while循环，因为high低于low。
That meant we have nothing more to search.
这意味着我们没有更多的搜索。
We have an empty array.
我们有一个空数组。
And therefore, we didn't find the element in the array.
因此，我们没有在数组中找到元素。
We're going to return low minus 1.
我们将返回低-1。
So the same result as the recursive version.
因此与递归版本的结果相同。
The difference is we won't be using the stack space that the recursive version uses.
不同之处在于我们不会使用递归版本使用的堆栈空间。
You remember we talked two videos ago about this real-life example where we had five languages and we were translating words between any two of those languages.
你记得我们之前谈过两个视频关于这个现实生活中的例子，我们有五种语言，我们正在翻译任何两种语言之间的单词。
The way we had that represented was parallel arrays, so that at any given index, each of the element in the arrays represented words that were the same in all those languages.
我们所代表的方式是并行数组，因此在任何给定的索引中，数组中的每个元素都代表所有这些语言中相同的单词。
So for instance, chair in English is at index two, and in Spanish that's silla and in Italian it's sedia.
因此，例如，英语主席在索引2，在西班牙语中是silla，在意大利语中是sedia。
The problem was it took a long time to look, right? We had 50,000 elements in our arrays, and it took like ten seconds for searching, because we had to really search through all of them if it wasn't there, on average, half of them, just 25,000.
问题是花了很长时间才看，对吧？我们的数组中有50,000个元素，搜索需要10秒钟，因为如果它不存在，我们必须真正搜索所有元素，平均而言，其中一半只有25,000个。
So one question might be, why didn't we use a sorted array? Right? You could imagine, for instance, sorting these arrays.
所以有一个问题，为什么我们不使用排序数组呢？对？例如，您可以想象对这些数组进行排序。
Here they're sorted.
他们在这里排序。
The good part is, it's easy to find a particular word in a particular language.
好的部分是，很容易找到特定语言的特定单词。
So I can find house in English, for instance, and find what index that is at very quickly, using binary search.
例如，我可以用英语找到house，并使用二进制搜索找到非常快的索引。
The problem is, I no longer have this correspondence, because the order of the words that are sorted in English is different from the order of the words sorted in Spanish.
问题是，我不再有这种对应关系，因为用英语排序的单词的顺序与用西班牙语排序的单词的顺序不同。
So if I look at chair, for instance, in English, it no longer maps to silla.
因此，如果我用英语看椅子，它就不再映射到新罗了。
So instead, if I look at chair and that's to casa.
所以相反，如果我看看椅子，那就是casa。
So although we can find a particular word in our source language, we don't know the corresponding word in the target language.
因此，尽管我们可以在源语言中找到特定单词，但我们不知道目标语言中的相应单词。
So the solution was to try and find some way we could do sorting and yet still preserve this relationship where everything at an index meant the same translated word.
因此，解决方案是尝试找到一些我们可以进行排序的方法，但仍保留这种关系，其中索引处的所有内容都意味着相同的翻译单词。
The way to do that was an augmented set of arrays.
这样做的方法是增加一组数组。
So what we really did was keep these augmented arrays which were pointers back into the original arrays in sorted order.
所以我们真正做的是将这些增强数组按指令排列回原始数组中。
So we're having a kind of level of indirection.
所以我们有一种间接的水平。
So if I look at English for example, the order of the words in English is chair, house, pimple.
因此，如果我以英语为例，英语单词的顺序是椅子，房子，疙瘩。
Well, what order is that in the original array? It is first element 2, and then element 1, and then element 3.
那么，原始数组中的顺序是什么？它是第一个元素2，然后是元素1，然后是元素3。
So if you want to do a binary search, you can use this sorted array.
因此，如果要进行二分查找，可以使用此排序数组。
Whenever you want to look at what an element is in that represented sorted array.
每当你想要查看表示排序数组的元素时。
So for instance, if we looked at the middle element, which in the sorted array is 2, it has the value 1 and that says go find house.
因此，例如，如果我们查看中间元素，它在排序数组中是2，它的值为1，并且表示找到房子。
So we basically, say house is sort of at element 2 and chair is at element 1 and pimple's at element 3.
所以我们基本上说，房子是元素2，椅子是元素1，疙瘩是元素3。
The Spanish, of course, has different mapping, so in Spanish, the first sorted word happens to be the first word in the array.
当然，西班牙语有不同的映射，所以在西班牙语中，第一个排序的单词恰好是数组中的第一个单词。
The second sorted word is the third word in the Spanish array; and the third sorted word, silla, is the second element.
第二个排序的单词是西班牙语数组中的第三个单词; 第三个排序单词silla是第二个元素。
So what happened when we ran this?
那么当我们跑这个时发生了什么？那么发生了什么，我们有一个时空交易。
We had to pay extra space.
我们不得不支付额外的空间。
And there were, of course, not only just English and Spanish sorted but also French, Italian, and German.
当然，不仅有英语和西班牙语，还有法语，意大利语和德语。
So, five arrays, extra arrays.
所以，五个数组，额外的数组。
Each array, had 50,000 entries in it and what was the size of each element of the array? Well, it represented a number from one to 50,000 that can be represented in 16-bits which is two bytes.
每个数组中有50,000个条目，数组中每个元素的大小是多少？好吧，它表示一个从1到50,000的数字，可以用16位表示，即两个字节。
So we had 50,000 elements times 2 bytes, that is 100,000 bytes times 5 is 500,000 bytes.
所以我们有50,000个元素乘以2个字节，即100,000个字节乘以5个是500,000个字节。
So about a half a megabyte, which today is almost nothing.
所以大约半兆字节，今天几乎没有。
And even then, was certainly doable 20 years ago.
即便如此，20年前肯定是可行的。
That's the cost we have in space.
这就是我们在太空中的成本。
What is the benefit that we get.
我们得到的好处是什么？
Well, instead of having to do let's say 50,000 look ups in the worst-case.
好吧，在最糟糕的情况下，不要让我们说50,000次查找。
Instead, we have to do log base two of 50,000 lock ups.
相反，我们必须做5万个锁定中的两个记录库。
So log base 2 of 50,000, that's about, let's see, log base of 1,000 is about ten because two to the ten equals 1024, so we have another factor of 50 to go.
所以记录基数2为50,000，那就是，让我们看一下，1000的对数基数大约为10，因为两个到十个等于1024，所以我们有另一个因子50。
Log base 2 of 50 is around, let's say six because I know that 2 to the 5th is equal 32, 2 to the 6th equals 64.
记录基数为50的50左右，比方说6，因为我知道2到5是等于32,2到6等于64。
So, what that means is, we have 16 references we have to do the array instead of 50,000.
那么，这意味着，我们有16个参考，我们必须做数组而不是50,000。
That's almost a factor of a thousand, so what that ended up meaning is that when the user clicks translate, instead of taking ten seconds, it was what appeared to be instantaneous.
这几乎是千分之一，所以最终的意思是，当用户点击翻译时，而不是花费十秒钟，这似乎是瞬间的。
It was well under a tenth of a second.
这还不到十分之一秒。
So in summary, what we've seen is that the runtime of binary search is big theta of log n.
总而言之，我们所看到的是二进制搜索的运行时间是log n的大值。
Substantially quicker than the big theta of n that linear search takes.
比线性搜索所需的n大的θ快得多。
So sorted arrays really help.
如此排序的数组确实有帮助
In the next lesson we're going to be looking at a more complicated application of divide and conquer, where we actually have multiple subproblems instead of just one subproblem.
在下一课中，我们将讨论一个更复杂的分而治之的应用，其中我们实际上有多个子问题而不是一个子问题。
------------- 33 -------------
01问题概述和天真的解决方案
In this lecture we're going to talk about a more complicated divide-and-conquer algorithm to solve polynomial multiplication.
在这个讲座中，我们将讨论一个更复杂的分而治之算法来解决多项式乘法。
So first we'll talk about what polynomial multiplication is.
首先我们将讨论多项式乘法是什么。
So polynomial multiplication is basically just taking two polynomials and multiplying them together.
因此，多项式乘法基本上只取两个多项式并将它们相乘。
It's used in a variety of ways in computer science.
它在计算机科学中以各种方式使用。
Error correcting codes, if you want to multiply large integers together.
如果要将大整数相乘，则纠错代码错误。
Right, so if you've got thousand digit integers and you want to multiply them together, there's a quicker way than doing it the normal way you learned in elementary school.
是的，所以如果你有千位数的整数并且想要将它们相乘，那么比在小学学习的正常方式更快。
And that uses the idea of multiplying polynomials.
这使用了乘法多项式的思想。
It is used for generating functions, and for convolution.
它用于生成函数和卷积。
Let's look at an example.
我们来看一个例子。
So let's say you have polynomial A, which is 3 x squared + 2x + 5, and polynomial B, which is 5 x squared + x + 2.
因此，假设您有多项式A，即3 x平方+ 2x + 5，以及多项式B，即5 x平方+ x + 2。
If you multiply them together you get 15 x to the fourth + 13 x cubed + 33 x squared + 9x + 10.
如果将它们相乘，则得到15 x到第四个+ 13 x立方+ 33 x平方+ 9x + 10。
Why is that? Well, let's look, for instance the 15 x to the fourth comes from multiplying 3 x squared times 5 x squared, that's 15x to the fourth.
这是为什么？那么，让我们看一下，例如，15 x到第四个来自3 x平方乘以5 x平方，即15x到第四个。
The 10 comes from multiplying 5 by 2.
10来自5乘以2。
The 13 x cubed comes from 3 x squared times x, which is 3 x cubed, plus 2x times 5 x squared, which is 10 x cubed.
13 x立方体来自3 x平方倍x，3 x立方，加2 x乘5 x平方，10 x立方。
For a total of 13 x cubed.
总共13 x立方。
So let's look at the problem statement.
那么让我们看一下问题陈述。
So we're going to have two n- 1 degree polynomials, all right? a sub n-1 is the coefficient of the x to the n-1 all the way down to a0 which is the coefficient of the x to the 0 term or the one term.
所以我们将有两个n-1次多项式，好吧？子n-1是x到n-1的系数，一直到a0，即x到0项或一个项的系数。
And then we similarly have a b polynomial as well.
然后我们同样也有ab多项式。
Now first you may wonder what happens if you actually want to multiply polynomials that don't happen to have the same degree? What if you want to multiply a degree three polynomial times a degree two polynomial? Right, where the degree is just the exponent of the highest term.
首先你可能想知道如果你真的想要乘以不具有相同度数的多项式会发生什么？如果你想将度数三次多项式乘以二次多项式怎么办？是的，学位只是最高学期的指数。
Well in that case, what you you could do is just pad out the smaller polynomial, the lower degree polynomial, to have zeros for its earlier coefficients.
那么在这种情况下，你能做的就是填充较小的多项式，即较低次多项式，使其早期系数为零。
I'll give an example of that in just a second.
我会在一秒钟内给出一个例子。
And then the product polynomial is the result that we want to come up with so that's a higher degree polynomial, right? If our incoming polynomials, are degree n- 1, then we're going to get a term of the x to the n- 1 in a, times x to the n- 1 in b, and that's going to give us an x to the 2n- 2 in the c term.
然后产品多项式是我们想要得到的结果，这是一个更高次多项式，对吗？如果我们的输入多项式是度数n-1，那么我们将得到一个x的项到a中的n-1，乘以x到n中的n-1，这将给我们一个x到c项中的2n-2。
So, the c sub 2n-2 term, comes about from multiplying the a sub n-1 term and the b sub n-1 term.
因此，c sub 2n-2项来自a sub n-1项和b sub n-1项的乘法。

So it's got two terms that multiply together.
所以它有两个术语相乘。
The c sub 2n-4 term would have three terms that multiply together.
c sub 2n-4术语将有三个术语相乘。
And we have more and more terms that get multiplied and summed together, and then fewer and fewer back down.
而且我们有越来越多的术语成倍增加并相加，然后越来越少的退缩。
So c sub 2 has three pairs which get added together, c sub 1 has two pairs and c sub 0 has one pair.
因此，c sub 2有三对加在一起，c sub 1有两对，c sub 0有一对。
So here's an example.
所以这是一个例子。
This is actually the same example we had before.
这实际上是我们之前的例子。
So n is three and all we need, notice, are the coefficients.
所以n是三，我们需要注意的是系数。
We don't actually need to have the x's written out.
我们实际上并不需要写出x。
So 3, 2, and 5 means 3 x squared plus 2x plus 5.
所以3,2和5意味着3 x平方加2x加5。
5, 1, 2 means 5 x squared plus x plus 2.
5,1,2表示5 x平方加x加2。
What if B were only a degree one polynomial? It was just x plus 2.
如果B只是一次多项式怎么办？它只是x加2。
Well then we would set B equal 0, 1, 2.
那么我们将B设置为0,1,2。
That is, B's x squared term is 0 x squared.
也就是说，B的x平方项是0 x平方。
So A(x) is this, B(x) is that.
所以A（x）就是这个，B（x）就是这个。
When you multiply them together, we get the same result we got before.
当你将它们相乘时，我们得到的结果与之前相同。
And now we just pluck off the coefficients here, so the 15, the 13, the 33, the 9, and the 10.
现在我们只是在这里取出系数，所以15,13,33,9和10。
And that's our resulting answer: those coefficients.
这就是我们得到的答案：那些系数。
So let's look at a naive algorithm to solve this.
那么让我们看一个天真的算法来解决这个问题。
The naive algorithm basically just says, well first off, let's create a product array.
天真的算法基本上只是说，首先，让我们创建一个产品数组。
This is basically going to be the C, the result, and it's going to be of highest degree 2n-2.
这基本上是C，结果，它将是最高度2n-2。
So it's going to have 2n-1 terms all the way from the 0 term up to the 2n-2 term.
所以它从0个词到2n-2个词一直有2n-1个词。
So we'll initialize it to 0, and then we'll have a nested for loop.
所以我们将它初始化为0，然后我们将有一个嵌套的for循环。
For i equals 0 to n-1, for j equals 0 to n-1.
对于i等于0到n-1，对于j等于0到n-1。
And at every time, what we'll do is we will calculate a particular pair.
而且每次我们要做的就是计算一对特定的一对。
So we'll calculate the A[i], B[j] pair, multiply them together and add them into the appropriate product.
因此，我们将计算A [i]，B [j]对，将它们相乘并将它们添加到适当的产品中。
Which is the appropriate product to put it in? It's the i + j case.
将它放入适当的产品中是哪种？这是i + j案例。
As an example, when i is 0 and j is 0, we calculate A at 0 times B at 0 and we add that to product at 0.
例如，当i为0且j为0时，我们在0处将A计算为0乘以B，并将其添加到0处的乘积。
So that says the two zero-degree terms in A and B get multiplied together to the zero-degree term in C.
这就是说A和B中的两个零度项一起乘以C中的零度项。
At the other extreme, if i is n-1 and j is n-1, we take A at n-1 times B at n-1 and we store that in the product of 2n-2.
在另一个极端，如果i是n-1且j是n-1，我们在n-1处取A的n-1倍，并将其存储在2n-2的乘积中。
As you can see, the intermediate values in product are going to have more terms added to them than the edges.
如您所见，产品中的中间值将添加更多的术语而不是边缘。

当然，然后我们返回产品。
How long does this take? Well, this takes order n squared.
这需要多长时间？好吧，这需要n平方的顺序。
Clearly, we've got two for loops, one smaller for loop that's from 0 to 2n-2, so that's order n.
显然，我们有两个for循环，一个小循环，从0到2n-2，所以这是n阶。
And then a nested for loop, where i goes from 0 to n-1, j goes from 0 to n-1, so those each go through the first one n times, the second one n squared times.
然后是一个嵌套的for循环，其中i从0变为n-1，j从0变为n-1，因此每个都经历n次n次，第二次n次平方次。
So our runtime is O(n squared).
所以我们的运行时间是O（n平方）。
In the next video, we're going to look at a divide and conquer algorithm to solve this problem.
在下一个视频中，我们将看一个分而治之的算法来解决这个问题。
Although, we'll see that it too will be somewhat naive.
虽然，我们会发现它也有些幼稚。
------------- 34 -------------
02天真分而治之算法
So let's look at a naive divide and conquer algorithm, to solve polynomial multiplication problem.
让我们看一个天真的分而治之算法，来解决多项式乘法问题。
The idea is, we're going to take our long polynomial and we're going to break it in two parts.
我们的想法是，我们将采用我们的长多项式，我们将分两部分进行分解。
The upper half and the lower half.
上半部分和下半部分。
So A(x) is going to be D sub one of X ,times x sub n over 2, plus d sub 0 of x, the bottom half.
所以A（x）将成为X中的D sub，乘以2中的x sub n，加上x的d sub 0，即下半部分。
D sub 1 of x, since we've pulled out x sub n over 2 terms, it's lowest term is actually, just a sub n over 2.
由于我们已经在2个项中拉出了x sub n，所以它的最低项实际上只是一个超过2的子n。
So we have two parallel sub polynomials, the high and the low.
所以我们有两个并行的子多项式，即高和低。
We do the same thing for B.
我们为B做同样的事情。
So we break that into E sub 1 of x, and E sub 0 of x.
所以我们把它分成x的E sub 1和x的E sub 0。
Again, where E sub 1 of x is the high terms, E sub 0 of x is the low terms.
同样，在x的E sub 1是高项的情况下，x的E sub 0是低项。
When we do our multiplication, then, we just multiply together D 1, x sub n over 2 plus D 0 and E 1 times x sub n over 2 plus E 0.
当我们进行乘法运算时，我们只需将D 1，x sub n乘以2加D 0和E 1乘以x sub n乘以2加E 0。
And that then yields for terms, D sub 1 E sub 1 times x sub n, D sub 1 E sub 0 + D sub 0 E sub 1 times x sub n/2 + D sub 0 E sub 0.
然后产生术语，D sub 1 E sub 1次x sub n，D sub 1 E sub 0 + D sub 0 E sub 1次x sub n / 2 + D sub 0 E sub 0。
The key here is that, we now just need to calculate D1 E1, D1 E0, D0 E1, and D0 E0.
关键在于，我们现在只需要计算D1 E1，D1 E0，D0 E1和D0 E0。
Those are all polynomials of degree n over 2.
这些都是n次超过2的多项式。
And so, now we can go ahead and use a recursive solution to solve this problem.
所以，现在我们可以继续使用递归解决方案来解决这个问题。
So it gives us a divide and conquer problem.
所以它给了我们一个分而治之的问题。
Its run time is T of n, equals 4 T of n over 2.
它的运行时间是T的n，等于4的n超过2。
Why 4? 4, because we're breaking into 4 subproblems.
为什么4？4，因为我们分成了4个子问题。
Each of them takes time T of n over 2 ecause the problem is broken in half.
由于问题被打破了一半，因此每个时间T取n超过2的时间。
Plus, then, in order to take the results and do our addition that's going to take order n time.
另外，为了获得结果并进行我们的添加，这将需要时间。
So some constant k, times that.
所以有些常数k，倍。
Let's look at an example.
我们来看一个例子。
So we have, n is 4, so we have degree three polynomials.
所以我们有，n是4，所以我们有三次多项式。
And we're going to break up A of x into the top half, 4x plus 3, and the bottom half, 2x plus 1.
而且我们要将A的x分为上半部分，4x加3，下半部分，2x加1。
Similarly, we're going to break up the top half of B of x.
同样，我们将打破x的B的上半部分。
X cubed plus 2 x squared just becomes x plus 2.
X立方加2 x平方只是x加2。
And 3x plus 4, stays at 3x plus 4.
3倍加4倍，3倍加4倍。
Now, we compute D1 E1.
现在，我们计算D1 E1。
So multiplying together, 4x + 3, times x plus 2, gives us 4 x squared + 11x + 6.
所以乘以4x + 3乘以x加2，得到4 x平方+ 11x + 6。
Similarly, we calculate D1 E0, D0 E1, and D0 E0.
同样，我们计算D1 E0，D0 E1和D0 E0。
Now we've done all four of those computations, AB is just D1 E1, 4 x squared + 11x + 6 times x to the 4th, plus the sum of D1 E0 and D0 E1, times x squared, plus finally D0 E0.
现在我们完成了所有这四个计算，AB只是D1 E1,4 x平方+ 11x + 6倍x到4，再加上D1 E0和D0 E1的总和，乘以x平方，再加上D0 E0。
If we sum this all together, we get 4 x to the 6th, plus 11 x to the 5th, plus 20 x to the 4th, plus 30 x cubed, plus 20 x squared, plus 11x plus 4.
如果我们将所有这些加在一起，我们得到4 x到6，加上11 x到5，加上20 x到4，再加上30 x立方，加上20 x平方，再加上11 x加4。
Which is our solution.
这是我们的解决方案。
Now, how long's this take to run? We're going to look at that in a moment.
现在，这需要多长时间才能运行？我们马上就会看一下。
Let's look at the actual code for it.
我们来看看它的实际代码。
So we're going to compute a resulting array, from 0 to 2n-2, so is all the results coefficients.
所以我们要计算一个结果数组，从0到2n-2，所有结果系数都是如此。
And our base case is that if n of size 1, we're going to multiply together A at a sub l, plus B at b sub l.
我们的基本情况是，如果大小为1的n，我们将在子l加上A加上b sub l加上B.
Let's look at those parameters again.
让我们再看看这些参数。
So A and B are our arrays of coefficients, n is the size of the problem, a sub l is the first coefficient that we're interested in.
所以A和B是我们的系数数组，n是问题的大小，sub l是我们感兴趣的第一个系数。
And b sub l is the coefficient in B, that we're interested in.
而b sub l是B中的系数，我们感兴趣。

And for n times.
并且n次。
First thing we'll do, is multiply together the D sub one and E sub one.
我们要做的第一件事就是将D sub one和E sub one相乘。
So basically what we're doing, I'm sorry, the D sub zero and E sub zero.
基本上我们正在做什么，对不起，D子零和E子零。
So, what we're doing is taking A and B, we're reducing the problem size by 2 and we're starting with those same coefficients.
所以，我们正在做的是采用A和B，我们将问题大小减少2，我们从相同的系数开始。
And we're going to assign those to the lower half of the elements in R.
我们将把这些分配给R中元素的下半部分。
Then we're going to do something similar, where we take the upper halves of each of A and B.
然后我们将做类似的事情，我们采取A和B各自的上半部分。
So again, the problem size becomes n/2, but now we're moving the lower coefficient we're interested in from a sub l to a sub l + n/2 and b sub l to b sub l + n/2.
再次，问题大小变为n / 2，但现在我们将我们感兴趣的较低系数从sub l移动到sub l + n / 2和b sub l到b sub l + n / 2。
And we're going to assign those to the high coefficients in our result.
我们将在结果中将这些分配给高系数。
Then, what we have to do is calculate D sub 0 E1, and D1 E0.
然后，我们要做的是计算D sub 0 E1和D1 E0。
And then, sum those together.
然后，将它们加在一起。
When we sum those together, we're going to assign those to the middle elements of the resulting array.
当我们将它们相加时，我们将把它们分配给结果数组的中间元素。
And we'll then return that result.
然后我们将返回该结果。
Now the question comes up, how long does it take? So we have an original problem of size n, we break it into four problems of size n over 2.
现在问题出现了，需要多长时间？所以我们有一个大小为n的原始问题，我们把它分成4个大小超过2的问题。
So, level 0 we have size n, level 1 we have size of n over 2, at level i, our problems are of size n over 2 to the i.
所以，级别0我们有大小n，级别1我们有n大小超过2，在级别i，我们的问题是大小n超过2到i。
And all the way down to the bottom of the tree is at log base 2 of n, and each of the problems are of size 1.
一直到树的底部是n的log 2，每个问题的大小都是1。
How many problems do we have? At level 0, we have 1 problem.
我们有多少问题？在0级，我们有1个问题。
We have then 4 problems.
我们有4个问题。
If we go to the i'th level, we have 4 to the i problems.
如果我们进入第i级，我们就会遇到4个问题。
And at the very bottom, then we have 4 to the log base 2 of n problems.
而在最底层，那么我们有4个问题的日志基数2。
How much work is there? Well, we just need to multiply together the number of problems times the amount of work, so we have kn here, and 4 times, 4 because there are 4 problems, kn over 2, because the problem size is n over 2 and the amount of work we're doing at each level is k times n over 2 per problem.
有多少工作？好吧，我们只需要将问题的数量乘以工作量，所以我们知道这里有4次，4次因为有4个问题，因此问题大小超过2且数量超过2我们在每个级别所做的工作是每次问题超过2次k次。
So 4 kn over 2 just equals k times 2n, At the ith level for the i problems, each problem takes k times n over 2 to the i to deal with, we multiply together, k 2 to the i times n.
所以4 kn超过2就等于k乘以2n，在i问题的第i级，每个问题需要k次n超过2来处理i，我们将它们相乘，k 2乘以i乘以n。
And at the very bottom, we have k amount of work, we have a problem size of 1, times 4 to the log base 2 of n.
在最底层，我们有大量的工作，我们有一个问题大小为1，乘以4到n的log 2。
Well four the log base two of n, is just n squared.
四个n的对数基数为2，只是n平方。
So we have k n squared.
所以我们已经知道了。
Our total as we sum up all the work is going to be summation from i equals zero to log base two of n of four to the i k times n over two to the i.
我们总结所有工作的总和将是从i等于零到记录基数为4的n中的两个到i的两倍到i的总和。
And that just gets dominated by the very bottom term which is big theta of n squared.
而这只是被n平方的大theta这个最底层的术语所支配。
So that's what our runtime takes.
这就是我们的运行时所需要的。
This is kind of weird.
这有点奇怪。
We went through all this work to create a divide and conquer algorithm.
我们完成了所有这些工作，以创建一个分而治之的算法。
And yet, the run time is the same run time as it was with our naive original algorithm.
然而，运行时间与我们天真的原始算法的运行时间相同。
We're going to see in the next video, a way to redo our divide and conquer algorithm, so we have less work to do at each level, and so we actually get a better final run time.
我们将在下一个视频中看到重做我们的分而治之算法的方法，因此我们在每个级别上都没有多少工作要做，因此我们实际上获得了更好的最终运行时间。
------------- 35 -------------
03更快的分而治之算法
In this video we'll look at creating a faster divide and conquer algorithm in order to solve the polynomial multiplication problem.
在这个视频中，我们将着眼于创建一个更快的分而治之算法，以解决多项式乘法问题。
This problem, this approach was invented by Karatsuba in the early 1960s.
这个问题，这种方法是由Karatsuba在20世纪60年代早期发明的。
So he was a graduate student of Komolgorov, a famous Russian mathematician.
所以他是俄罗斯着名数学家科莫戈罗夫的研究生。
And Komolgorov theorized that n squared was the best that one could do.
而Komolgorov认为，n平方是最好的。
So there was a lower bound of n squared, doing polynomial multiplication.
所以有一个n平方的下界，做多项式乘法。
Karatsuba, a grad student, heard the problem, went away, came back a week later with a solution.
研究生Karatsuba听到了这个问题，离开了，一周后回来找了解决方案。
So let's look at what is involved.
那么让我们看一下所涉及的内容。
So if we look at A(x) it's just a very simple polynomial, a1x + a0.
因此，如果我们看A（x），它只是一个非常简单的多项式，a1x + a0。
And B(x) = b1x + b0, and then C(x) is, what would match in there? a1b1x squared + (a1b0 + a0b1)x + a0b0.
并且B（x）= b1x + b0，然后是C（x），那里会匹配什么？a1b1x平方+（a1b0 + a0b1）x + a0b0。
So we'll notice here we need four multiplications.
所以我们在这里注意到我们需要四次乘法运算。
We need to multiply a1 times b1.
我们需要乘以a1乘以b1。
We need to multiply a1 times b0, a0 times b1, and a0 times b0.
我们需要乘以a1乘以b0，a0乘以b1，a0乘以b0。
This is how we did the divide and conquer in fact in our last video.
这就是我们在上一个视频中实现分歧和征服的方式。
So we need four multiplications.
所以我们需要四次乘法。
Karatsuba's insight was that there was a way to re-write C(x), so that you only needed to do three multiplications.
Karatsuba的见解是有一种方法可以重写C（x），所以你只需要做三次乘法。
So basically what he did is he re-wrote that inner term, a1b0 + a0b1 as something slightly more complicated.
所以基本上他所做的就是重写那个内部术语，a1b0 + a0b1稍微复杂一些。
So he added together, (a1 + a0) (b1 + b0).
所以他加在一起，（a1 + a0）（b1 + b0）。
So (a1 + a0) (b1 + b0) is just a1b1 + a0b1 + a1b0 + a0b0.
所以（a1 + a0）（b1 + b0）只是a1b1 + a0b1 + a1b0 + a0b0。
And then he subtracted out the a1b1 and the a0b0, so he's left with a1b0 + a0b1.
然后他减去了a1b1和a0b0，所以他留下了a1b0 + a0b1。
Which is exactly what's there to begin with.
这正是从那开始的。
The key here though, is how many multiplications are needed.
这里的关键是需要多少次乘法。
It only needs three multiplications.
它只需要三次乘法。
We need to compute a1 b1, even though we use it twice.
我们需要计算a1 b1，即使我们使用它两次。
We need to compute a0 b0, even again, though we use it only twice.
我们需要再次计算a0 b0，尽管我们只使用它两次。
And then we need to multiply together (a1 + a0) and (b1 + b0).
然后我们需要将（a1 + a0）和（b1 + b0）相乘。
So we do have some extra additions.
所以我们确实有一些额外的补充。
But the key is, when we have three multiplications instead of four.
但关键是，当我们有三次乘法而不是四次。
Why does this matter? Well, why it matters is because we are reducing the number of problems at each level.
为什么这很重要？那么，重要的是因为我们正在减少每个级别的问题数量。
But let's first look at an example.
但我们先来看一个例子。
So here we've got A(x).
所以这里我们有A（x）。
We're going to have 4 x cubed + 3 x squared + 2x +1.
我们将有4 x立方+ 3 x平方+ 2x +1。
B(x) = x cubed + 2 x squared + 3x + 4.
B（x）= x立方+ 2 x平方+ 3x + 4。
We're going to go ahead and pull out D1 and D0 like we did before.
我们将像以前一样继续推出D1和D0。
In our divide and conquer.
在我们的分而治之。
The key is what we're going to actually do in terms of the subproblems.
关键是我们要在子问题上实际做的事情。
So we have D1 and D0.
所以我们有D1和D0。
We have E1 and we have E0.
我们有E1，我们有E0。
We're going to compute D1 E1, again, just like we did before.
我们将再次计算D1 E1，就像我们之前一样。
We're going to compute D0 E0, again just like we did before.
我们将再次计算D0 E0，就像我们之前一样。
But now we won't compute D1 E0 and D0 E1.
但现在我们不会计算D1 E0和D0 E1。
Instead we're going to sum together D1 and D0.
相反，我们要把D1和D0加在一起。
Sum together E1 and E0.
将E1和E0相加在一起。
So (D1 + D0) is going to be (6x + 4).
所以（D1 + D0）将是（6x + 4）。
(E1 + E0) is going to be (4x plus 6).
（E1 + E0）将是（4x加6）。
And then we multiply those two polynomials together, yielding 24 x squared + 52x + 24.
然后我们将这两个多项式相乘，得到24 x平方+ 52x + 24。
So, so far, how many multiplications have we done? Three.
那么，到目前为止，我们做了多少次乘法？三。
And then, our final result for A(x) B(x) is D1E1 times x to the fourth +, now what do we do here? We take that (D1 + D0) (E1 + E0).
然后，我们对A（x）B（x）的最终结果是D1E1倍x到第四个+，现在我们在这做什么？我们取（D1 + D0）（E1 + E0）。
(24x squared + 52x + 24), okay? Add that in the second term.
（24x平方+ 52x + 24），好吗？在第二学期添加。
And then subtract out D1 E1.
然后减去D1 E1。
Subtract out D0 E0.
减去D0 E0。
And then our final term will be D0 E0.
然后我们的最终用语将是D0 E0。
If we simplify that middle portion, and all of it.
如果我们简化中间部分，以及所有部分。
We just end up with 4 x to the sixth + 11 x to the fifth + 20 x to the fourth + 3 x cubed + 20 x squared + 11x + 4.
我们最终得到4 x到第六+ 11 x到第五+ 20 x到第四+ 3 x立方+ 20 x平方+ 11x + 4。
Which is the exact same result we got doing it in the more naive divide and conquer.
这是我们在更天真的分而治之中做到的完全相同的结果。
And also the same way we'd do it if we did a straight naive problem, okay? So we get the same result, three multiplications instead of four multiplications.