如果我们做一个直接天真的问题，我们也会这样做，好吗？所以我们得到相同的结果，三次乘法而不是四次乘法。
That extra multiplication makes a big difference.
额外的乘法会带来很大的不同。
Let's look at our runtime.
我们来看看我们的运行时。
So our initial problem is of size n.
所以我们最初的问题是大小为n。
When we break it down, we have three problems of size n over 2, again, rather than 4.
当我们分解它时，我们有三个大小为n超过2的问题，而不是4。
So level 0, problem size n.
所以级别0，问题大小n。
Level 1, a problem of size n over 2.
等级1，大小为n超过2的问题。
At level i, our problems are of size n over 2 to the i, just like they were in the other divide and conquer problem.
在第一级，我们的问题是大小超过2的i，就像他们在另一个分而治之的问题。
And we have the same number of leaves.
我们有相同数量的叶子。
So at log base 2 of n level, all the problems are of size 1.
所以在n级的log 2中，所有问题都是1。
And the number of problems that we have, 1 of them at level 0, 3 instead of 4 at level 1, 3 to the i.
我们遇到的问题数量，其中1个在0级，3个而不是4级，1级，3个。
instead of 4 to the i, at level i.
在i级，而不是4到i。
And 3 to the log base 2 of n, instead of 4 to the log base, 2 of n at the bottom level.
并且3到n的对数基数2，而不是4到对数基数，2到n的底层。
How much work? We'll multiply together, so we'll figure out for each problem how much it takes.
多少工作？我们将一起繁殖，因此我们将为每个问题找出需要多少的问题。
In this case at level 0 it's kn.
在这种情况下，在0级它是kn。
At level 1, each problem takes k(n/2) work.
在级别1，每个问题需要k（n / 2）个工作。
And there are three of them.
其中有三个。
So it's k(3/2) n.
所以它是k（3/2）n。
At the ith level, we end up with k times (3/2) to the i times n.
在第i级，我们最终得到k次（3/2）到i次n。
And at the bottom level, k times 3 to the log base 2 of n.
并且在底层，k乘以3到n的对数基数2。
a to the log base b of c, is the same thing as c to the log base b of a.
a到c的log对象b，与a的log对象b的c相同。
So therefore this is the same as kn to the log base 2 of 3.
因此，这与3的对数基数2的kn相同。
We sum those, summation from i = zero to log base 2 of n of 3 to the i times k times n over 2 to the i.
我们总结那些，从i = 0到n的3的对数基数2到i乘以2的k倍n乘以i。
This is bounded, it's this geometric series bounded by the last term.
这是有限的，它是由最后一个术语限定的几何系列。
Which is big Theta of n to the log base 2 of 3.
哪个是n的大Theta到3的基数2。
Log base 2 of 3 is about 1.58.
2的对数基数约为1.58。
So, we now have a problem where our solution is big Theta of n to the 1.58.
所以，我们现在遇到的问题是我们的解决方案是n到1.58的大Theta。
Compared to our original problem, which had a big Theta of n squared solution.
与我们原来的问题相比，它有一个很大的θ平方解决方案。
So this makes a huge difference as n gets large, in terms of our final runtime.
因此，就最终运行时而言，当n变大时，这会产生巨大的差异。
It's not uncommon for divide and conquer algorithms sometimes to require sort of a way of looking at it in terms of breaking up a problem.
分裂和征服算法有时需要某种方式来分解问题，这种情况并不少见。
So that you have fewer subproblems.
这样你就可以减少子问题。
And because of the compounding of the fact that the more subproblems at a level, you have more, and more, and more.
并且由于在一个级别上存在更多子问题这一事实的复合，您拥有更多，更多，更多。
Reducing the number of subproblems, reduces the final runtime.
减少子问题的数量，减少最终的运行时间。
------------- 36 -------------
01什么是主定理
Here we're going to talk about the master theorem.
在这里，我们将讨论主定理。
We'll describe what the master theorem is and how to use it.
我们将描述主定理是什么以及如何使用它。
And we'll reserve to the next video a proof.
我们将保留下一个视频的证明。
So we've had many occasions where we have had to write a recurrence relation for a divide and conquer problem.
所以我们曾经有过许多场合，我们不得不为分而治之的问题写一个递归关系。
This is an example of one for binary search.
这是二进制搜索的示例。
We break a problem down into a problem half as big and we do a constant amount of work at each level.
我们将问题分解为一半大的问题，并且我们在每个级别进行一定量的工作。
And this gives us a solution T(n) = O(log n).
这给了我们一个解T（n）= O（log n）的解。
The problem is for each one of these we have to create a recurrence tree, figure out how much work is done at each level, sum up that work.
问题是每一个我们必须创建一个递归树，计算每个级别完成了多少工作，总结这项工作。
That's a lot to do to solve each recurrence relation.
要解决每个递归关系，还有很多工作要做。
Here's an example that we used for the polynomial multiplication.
这是我们用于多项式乘法的一个例子。
So we broke a problem into four sub-problems, each half the size, and did a linear amount of work.
因此，我们将问题分解为四个子问题，每个问题的大小只有一半，并且做了一系列线性工作。
And the solution was T(n) = O(n squared).
并且解决方案是T（n）= O（n平方）。
When we had the more efficient algorithm, where we had only three sub-problems instead of four, we then got a solution of O(n to the log base 2 of 3).
当我们有更高效的算法时，我们只有三个子问题而不是四个子问题，然后我们得到一个O的解（n到3的对数基数为2）。
Sometimes we break a problem into only two subproblems and there the solution is O(n log n).
有时我们只将问题分解为两个子问题，解决方案是O（n log n）。
So, wouldn't it be nice if there was a way that we just had a formula to tell us what the solution is rather than having to create this recurrence tree each time? And that's what the Master Theorem basically does.
那么，如果我们只有一个公式来告诉我们解决方案是什么而不是每次都必须创建这个重复树，那不是很好吗？这就是主定理基本上做的。
So, the Master Theorem says if you have a recurrence relation T(n) equals a, some constant, times T( the ceiling of n divided by b) + a polynomial in n with degree d.
所以，主定理说如果你有一个递推关系T（n）等于a，一些常数，乘以T（n的上限除以b）+ n中的多项式，其中d为d。
And that ceiling, by the way, could just as well be a floor or not be there at all if n were a power of b.
顺便说一下，如果n是b的力量，那么天花板也可以是一个地板，或者根本不存在。
In any case, the a is a constant greater than 0.
在任何情况下，a都是大于0的常数。
b is greater than 1 because we want to actually make sure the problem size gets smaller.
b大于1，因为我们希望确实确保问题大小变小。
And d is greater than equal to 0.
并且d大于等于0。
Well, in that case, we have a solution for T of n.
那么，在这种情况下，我们有一个解决T的n。
There are three sub cases.
有三个子案例。
Case number 1, and all of these cases depend on the relationship between d, a, and b.
案例编号1，所有这些案例都取决于d，a和b之间的关系。
In particular, is d greater than log base b of a? If so, the solution is just this polynomial in n, O(of n to the d).
特别是，d大于log的基数b？如果是这样，解决方案只是n，O（n到d）的多项式。
If d is exactly equal log base b of a, then the solution is big O of n to the d with an extra factor of log n.
如果d恰好等于a的log base b，那么解决方案是d的大O，其中log n的额外因子。
And finally, if d is less than log base b of a, then the solution is big O of n to the log base b of a.
最后，如果d小于a的log b，那么解决方案是a的大O到a的log b。
So let's look at some applications of this theorem.
那么让我们来看看这个定理的一些应用。
So here's one where we go back to the polynomial multiplication.
所以这是我们回到多项式乘法的地方。
Here a is 4, b is 2, and d is 1.
这里a是4，b是2，d是1。
Because O(n) is just O(n to the 1).
因为O（n）只是O（n到1）。
And we look at the relationship between d, which is 1, and log base b of a, which is log base 2 of 4 or 2.
我们来看看d（1）和a的log base b之间的关系，它是4或2的对数基数2。
Well clearly d is less than log base b of a, so we're in case three.
很明显d小于a的log b，所以我们就是三个。
Therefore T(n) = O(n to the log base b of a), or just O(n squared).
因此，T（n）= O（对于a的对数基数b为n），或者仅为O（n的平方）。
If now we change the 4 to a 3, a is 3, b is 2, d is 1.
如果现在我们将4改为3，a为3，b为2，d为1。
Now d is still less than log base b of a because log base 2 of 3 is greater than 1, and so again we're in case three.
现在d仍然小于a的log base b，因为3的log base 2大于1，所以我们再次讨论3。
T(n) equals O(n to the log base b of a), which equals O(n to the log base 2 of 3).
T（n）等于O（n对应于a的对数基数b），等于O（n对数基数2为3）。
If we reduce the 3 down to a 2 what happens? Well here, a is 2, b is 2, d is 1.
如果我们将3减少到2会发生什么？那么，a是2，b是2，d是1。
Log base b of a is log base 2 of 2, which is just 1.
a的log base b是2的log 2，也就是1。
So now d is equal log base b or a.
所以现在d等于log base b或a。
We're in case two now.
我们现在遇到两个。
And so, T of n equals O(n log n).
因此，n的T等于O（n log n）。
And now this shows an example also of case two.
现在，这也显示了案例二的一个例子。
So this is the binary search example.
所以这是二进制搜索示例。
A is 1, b is 2, d is 0.
A是1，b是2，d是0。
Well the log base two of one, log base b of a, is equal to zero.
那么一个日志库中的两个，a的基数b，等于零。
So d is equal to log base b of a.
所以d等于a的log base b。
We're in case two, T(n) = O(n to the d log n), which is in the 0 log n, which is just O(log n).
我们遇到两种情况，T（n）= O（n到n log n），它在0 log n中，它只是O（log n）。
And a final example where we are actually in case one.
最后一个例子，我们实际上是一个例子。
So here a is 2, b is 2, and d is 2.
所以这里a是2，b是2，d是2。
So log base b of a is log base 2 of 2, which is one.
所以a的log base b是log 2的2，即1。
So d is now greater than log base b of a.
所以d现在大于a的log base b。
We are now in case one, T(n) equals O(n to the d), which is O(n squared).
我们现在处于第一种情况，T（n）等于O（n到n），即O（n平方）。
So what we've seen now is that we have this master theorem that allows us, for most recurrences, when you do a divide and conquer which fit into this general formula, allows us to easily figure out which case we are based on the relationships between a, b, and d.
所以我们现在看到的是，我们有这个主要定理，允许我们，对于大多数复发，当你进行符合这个通用公式的分而治之时，允许我们轻松地找出我们基于关系的情况a，b和d之间。
And then figure out the result quite quickly.
然后很快找出结果。
In our next video we'll look at a proof of why the master theorem works.
在我们的下一个视频中，我们将看一下主定理为何起作用的证明。
------------- 37 -------------
02证明了主定理
In this video, we'll look at a proof of how the Master Theorem works.
在本视频中，我们将看一下主定理如何工作的证明。
So a reminder, the Master Theorem states that if T(n) equals a T of ceiling of n over b plus a polynomial, then we have these three cases.
所以提醒一下，主定理指出，如果T（n）等于n超过b的上限T加上多项式，那么我们就有这三种情况。
So let's do as we normally do with a recurrence relation and let's create a recurrence tree.
因此，让我们像往常一样使用递归关系，让我们创建一个递归树。
So we'll have our recurrence at the top to just remind ourselves what that is.
因此，我们将在顶部再次发生，以便提醒自己这是什么。
Let's assume for the sake of argument that n is a power of b.
让我们假设为了论证n是b的幂。
That's a reasonable assumption since we can always just pad n to be larger, right, if we increase it by no more than b we can get to the next closest power of b and then this will be a simpler analysis.
这是一个合理的假设，因为我们总是可以将n填充为更大，对，如果我们将它增加不超过b，我们可以得到b的下一个最接近的幂，然后这将是一个更简单的分析。
So we have our problem n.
所以我们有问题。
At the next level, we break the problem down into a copies of a problem n over b large.
在下一个级别，我们将问题分解为b大问题的副本。
So level zero.
所以零级。
We have a problem of size n.
我们有一个大小为n的问题。
Level 1 we have problems of size n/b.
1级我们有大小n / b的问题。
At the general level i we have problems of size n over b to the i.
在一般水平上，我们在i上遇到大小为n的问题。
At the bottom level, which is level log base b of n, we have problems of size 1.
在底层，即n的级别log base b，我们遇到大小为1的问题。
How many problems are there? At level 0 there's of course one problem.
有多少问题？在0级，当然有一个问题。
At level 1, a problems.
在1级，出现问题。
And in general at the ith level, a to the i problems.
一般来说，在第i级，对于我的问题。
At the log base b of n level, it's a to the log base b of n.
在n级的log对数b中，它是n的log对数b。
How much work do we have to do? Well work is just a function of how many problems we have and the amount of work for each problem.
我们需要做多少工作？好的工作只是我们有多少问题以及每个问题的工作量的函数。
So at level zero we have just O(n to the d) work.
所以在零级我们只有O（n到d）的工作。
There's one problem and it takes O(n to the d) time.
有一个问题，需要O（n到d）时间。
And level one we have a problems.
一级我们有问题。
And each of them takes O(n over b to the d) work.
并且每个人都需要O（n over b到d）工作。
Okay, we can pull out the a and the b and the d to be all together, and that's just O(n to the d) times a over b to the d.
好的，我们可以将a和b以及d拉出来，这就是O（n到d）乘以d到d。
At the ith level we have a to the i problems and each one is O(n over b to the i to the d).
在第i级，我们有一个问题，每一个都是O（n到b到i到d）。
Again, we can pull out the a to the i, the b to the i, and we're left with O(n to the d) times a over b to the d to the i.
再一次，我们可以将a拉出到i，将b拉到i，然后我们留下O（n到d）乘以b到d到i。
And finally, at the bottom level it's just a to the log base b of n because the problems are all size 1.
最后，在底层，它只是n的log a b，因为问题都是1。
It's just O(n to the log base b of a).
它只是O（对于a的对数基数b）。
So the total amount of work is the summation from 0 to the log base b of n.
因此总工作量是从0到n的对数基数b的总和。
O(n to the d) times the quantity a over b to the d, all that to the i.
O（n到d）乘以a到b的数量a，到i的所有数量。
So let's look at what seems like a slight digression, and that is geometric series.
那么让我们看看看起来像是一个轻微的题外话，那就是几何系列。
So a Geometric Series is a series of numbers that progresses by some multiplicative factor.
所以几何系列是一系列由一些乘法因子推进的数字。
I'll give you an example.
我给你举个例子。
If we take 1 + 2 + 4 + 8 + 16 + 32 + 64, that's a geometric series where our factor is a factor of 2 at each time.
如果我们取1 + 2 + 4 + 8 + 16 + 32 + 64，这是一个几何系列，其中我们的因子每次都是2。
Just as well, we could have a geometric series that goes down.
同样，我们可能会有一个下降的几何系列。
So we could have, for instance, let's say 10,000, 1,000, 100, 10, 1.
例如，我们可以说10,000,1,000,100,10,1。
Where we're going down by a constant factor of ten at each increment.
我们在每个增量下降10个常数因子。
Now it turns out, our multiplicative factor, let's call that r, as long as r is not equal to one we have a simple closed form for this.
现在事实证明，我们的乘法因子，我们称之为r，只要r不等于1，我们就有一个简单的闭合形式。
This is just a times (1-r) to the n over 1 minus r.
这只是n超过1减去r的一倍（1-r）。
And it turns out that big O notation, what happens is we care about the largest term.
事实证明，大O符号，我们关心的是最大的术语。
So our sum is going to be bounded by a constant times our largest term.
因此，我们的总和将受到我们最大术语的恒定时间的限制。
So, if r is less than 1 then our largest term is the first element a and therefore our solution is O(a).
因此，如果r小于1，那么我们最大的项是第一个元素a，因此我们的解是O（a）。
Okay, because it's our largest term, it gets smaller, smaller, smaller, smaller, smaller.
好吧，因为它是我们最大的术语，它变得更小，更小，更小，更小，更小。
And as long as it's by this multiplicative factor, then all that really matters is this first term, because the rest of it sums to no more than a constant times that first term.
只要它是乘以这个乘法因子，那么真正重要的就是第一个项，因为其余部分总和不超过第一项的恒定时间。
If on the other hand, r is greater than 1, then what matters is the very last term, because that's the biggest term and all the previous ones are smaller and smaller.
另一方面，如果r大于1，那么重要的是最后一个术语，因为这是最大的术语，而之前的所有术语都越来越小。
So it's smallest, larger, larger, larger, largest.
所以它是最小的，更大的，更大的，更大的，最大的。
And so that largest term is a r to the (n-1).
所以最大的术语是（n-1）。
So in a geometric series we care about either the first term or the last term, whichever one is bigger.
因此，在几何系列中，我们关心的是第一项或最后一项，无论哪一项更大。
Now if we take that back to the case of our recurrence tree, we notice our summation here.
现在，如果我们回到我们的重复树的情况，我们在这里注意到我们的总结。
This is the same summation we had from our recurrence tree and we see that we have a geometric series.
这与我们从递归树得到的总和相同，我们看到我们有一个几何系列。
a is taking the place of big O then to the d and r is taking the place of a over b to the d.
a取代大O然后到d，r代替d到d。
So our multiplicative factor is a over b to the d.
所以我们的乘法因子是d的b。
And there are three cases.
有三种情况。
You remember as we stated the solution to the Master Theorem.
你记得我们说过主定理的解决方案。
Case one is d is greater than log base b of a.
情况一是d大于a的log base b。
Well it's equivalent to saying a over b to the d is less than 1.
嗯，这相当于说d超过b小于1。
So now we have our multiplicative term is less than 1.
所以现在我们的乘法项小于1。
So it's getting smaller and smaller and smaller.
所以它变得越来越小越来越小。
That means that the largest term is the first term.
这意味着最大的术语是第一个术语。
And that's the one that we have an order of.
这就是我们订购的那个。
So this is big O of, officially big O of big O of n to the d, which is just the same as big O of n to the d.
所以这是d的大O的正大O，这与d的大O相同。
Case 2, where d equals log base b of a and equivalently, a over b to the d is equal 1.
情况2，其中d等于a的对数基数b，并且等效地，对于d的a over b等于1。
Well, if a over b to the d is equal to one, remember our geometric series formula didn't hold, so we're going to just have to calculate this.
好吧，如果对于d的过度b等于1，请记住我们的几何级数公式不成立，所以我们只需要计算它。
But if a over b to the d is 1, then a over b to the d to any power is still 1.
但是如果对于d的过度b是1，则对于任何功率的过量b仍为1。
So that means, that our summation is just a summation from i equals 0 to log base b of n of O(n to the d).
这意味着，我们的求和只是从i等于0到n的n（n到d）的log b的求和。
And that's just 1 plus log base b of n, because that's the number of terms in our summation times O(n to the d).
而且这只是n加上n的对数基数b，因为这是我们求和时间O（n到d）中的项数。
Well the 1 is a low order term we don't care about, and log base b of n can just be treated as log n, because a base change is just some multiplicative factor, and that disappears in our big O notation.
那么1是我们不关心的低阶项，并且n的log log b可以被视为log n，因为基数变化只是一些乘法因子，并且在我们的大O表示法中消失。
So we end up with, as we see in the theorem, O(n to the d times log n).
因此，正如我们在定理中看到的那样，我们最终得到O（n到d次log n）。
And then our final case, is d is less than log base b of a, which is equivalent to saying a over b to the d is greater than 1.
然后我们的最后一种情况是，d小于a的log b，这相当于说d超过b大于1。
So here, our multiplicative factor is greater than 1.
所以在这里，我们的乘法因子大于1。
So our smallest term is the first term and our largest term is the last term.
因此，我们的最短期限是第一个期限，我们最大的期限是最后一个期限。
So in this case, this is big O of our last term is O(n to the d) times a over b to the d to the log b of n.
所以在这种情况下，这是我们最后一个术语的大O是O（n到d）乘以b到d到n的log b。
So, i is log base b of n.
所以，我是n的日志基数b。
This is a bit of a mess.
这有点乱。
Let's see whether we can fix this a little bit.
让我们看看我们是否可以解决这个问题。
So let's go ahead and apply the log base b of n power separately to a and b to the d.
那么让我们继续将n幂的log base b分别应用于a和b到d。
So we have, in the numerator, a to the log base b of n.
所以我们在分子中得到了n的对数基数b。
And then the denominator, b to the d times log base b of n.
然后是分母，b到d次记录n的基数b。
Well, b to the log base b of n is just n.
那么，b到n的对数基数b只是n。
So, that's going to disappear down to n to the d in the denominator.
所以，这将在分母中消失到n。
In the numerator, a to the log base b of n, by logarithmic identity is equal to n to the log base b of a.
在分子中，对于n的对数基数b，通过对数标识等于n到a的对数基数b。
So we can swap those other two.
所以我们可以交换其他两个。
And now, if we compare big O of n to the d and n to the d, we know big O of n to the d is bounded by some constant, k times n to the d.
而现在，如果我们将n的大O与d和n与d进行比较，我们知道d的大O是由一个常数限定的，k是n的d。
So we have k n to the d divided by n to the d, which is just some k.
所以我们将d除以n除以d，这只是k。
And that constant can go away because we're still talking about big O notation.
而这个常数可以消失，因为我们仍然在谈论大O符号。
So we're left just with big O of n to the log base b of a, which is what we have for the final case.
所以我们只剩下一个大的O到n的a的基数b，这就是我们对最终案例的看法。
So the Master theorem is a shortcut.
因此，Master定理是一种捷径。
Our master theorem again as a restatement is here.
我们的主要定理再次作为重述就在这里。

不过，我有个秘密要告诉你。
I do not remember the master theorem and I don't actually even look up the master theorem.
我不记得主定理，我甚至不查看主定理。
Here's what I do.
这就是我的工作。
When I have a recurrence of this rough form, I look at the amount of work done at the first level and at the second level (which is a very easy calculation) and then I just say to myself Is that the same amount of work? If it's the same amount of work it's going to be the same amount of work all the way down and so we're going to be in case two.
当我再次出现这种粗糙的形式时，我会看一下在第一级和第二级完成的工作量（这是一个非常简单的计算）然后我只是对自己说这是相同的工作量吗？如果它的工作量相同，那么一直都是相同的工作量，所以我们将会遇到两个问题。
So it's going to be the amount of work at the first level, which we known is O(n to the d), times log n because there are that many levels.
所以它将是第一级的工作量，我们称之为O（n到d），乘以log n因为有很多级别。
On the other hand, if the first term is larger than the second term I know the first term is going to dwarf all the other terms.
另一方面，如果第一个术语大于第二个术语，我知道第一个术语将使所有其他术语相形见绌。
And so, we're left with just O(n to the d).
所以，我们只剩下O（n到d）。
And finally, if the first term is less than the second term, I know they're going to keep increasing and it's the bottom term that I need.
最后，如果第一学期少于第二学期，我知道他们将继续增加，这是我需要的最低学期。
And that is just going to be the number of leaves which is n to the log base b of a.
而这只是叶子的数量，它是a的对数基数b的n。
The master theorem is really handy to use whether you memorize it or you have it written down and use it or in my case you sort of recreate it every time you need it.
掌握定理非常方便使用，无论你是记住它还是记下它并使用它，或者在我的情况下，你可以在每次需要时重新创建它。
Thanks.
谢谢。
------------- 38 -------------
01问题概述
Hello, and welcome to the sorting problem lesson.
您好，欢迎来到排序问题课程。
As usual, we start with a problem I'll review.
像往常一样，我们从一个问题开始，我将审查。
So sorting is a fundamental computational problem.
因此排序是一个基本的计算问题。
Your input in this problem consists of a sequence of elements, and your goal is to output this element in, for example, non-decreasing order.
您在此问题中的输入由一系列元素组成，您的目标是以非递减顺序输出此元素。
The formal statement of this problem is as follows.
该问题的正式陈述如下。
You are given a sequence of finite elements.
您将获得一系列有限元素。
We will usually denote the sequence by A throughout this lesson.
在本课程中，我们通常用A表示序列。
And your goal is to output these same elements in non-decreasing order.
您的目标是以非递减顺序输出这些相同的元素。
Once again, sorting is an important computational task used in many efficient algorithms.
再次，排序是许多有效算法中使用的重要计算任务。
For some algorithms, it is just as important to process given elements in non-decreasing order, going from smaller ones to larger ones.
对于某些算法，以非递减顺序处理给定元素同样重要，从较小的到较大的。
In some other algorithms, just by sorting your input data, you gain a possibility to perform your queries much more efficiently.
在其他一些算法中，只需对输入数据进行排序，就可以更有效地执行查询。
A canonical example of such situation is a search problem.
这种情况的典型例子是搜索问题。
In this problem, we are given a sequence of finite elements.
在这个问题中，我们给出了一系列有限元。
And your goal is to check whether a particular element is present in your sequence.
您的目标是检查序列中是否存在特定元素。
A simple way to solve this problem, is of course, just to scan your input sequence from left to right and to check, whether your element is present in this sequence.
解决此问题的一种简单方法当然是从左到右扫描输入序列并检查元素是否存在于此序列中。
This gives you a linear kind algorithm.
这为您提供了线性类算法。
And you know already that if you input data, if you input sequences you sorted, then you can do this much more faster.
而且你已经知道，如果你输入数据，如果输入你排序的序列，那么你可以更快地完成这项工作。
Basically, in time, in logarithmic time, in the size of your input sequence.
基本上，在对数时间内，在输入序列的大小。
So ou first compare your element to the middle element.
所以你首先要比较你的元素和中间元素。
If it is just few element, then you are done, if it is not, you continue with the left half of your sequence or the right half of your sequence.
如果它只是少数元素，那么你就完成了，如果不是，你继续你的序列的左半部分或序列的右半部分。
So in logarithmic number of comparison, and the worst case, you will be able to say whether your element is present in this sequence or not.
因此，在对数的比较和最坏的情况下，您将能够说明您的元素是否存在于此序列中。
So, if you are given a sequence and you are expecting many such queries.
所以，如果给你一个序列，你期待很多这样的查询。
You're expecting to be asked to check whether a given object is present or not.
您希望被要求检查给定对象是否存在。
For me such objects, then it just makes sense to first sort your input data and only then perform all these queries.
对于我这样的对象，那么首先对输入数据进行排序然后才执行所有这些查询才有意义。
This will give you a much more efficient algorithm in general.
这将为您提供更高效的算法。
All right.
好吧。
And this is only a small example.
这只是一个小例子。
We will see many other situations, where sorting your data first helps to perform queries much more efficiently.
我们将看到许多其他情况，首先对数据进行排序有助于更有效地执行查询。
So in the subsequent videos of this lesson, we will study many efficient sorting algorithms.
因此，在本课的后续视频中，我们将研究许多有效的排序算法。
------------- 39 -------------
02选择排序
In this video, we will study one of the simplest sort of algorithms called selection sort.
在本视频中，我们将研究一种称为选择排序的最简单的算法。
So it's main idea is quite simple, we just keep growing the sorted part of our rate.
所以它的主要思想很简单，我们只是继续增加我们的速率的分类部分。
So let me illustrate it on a toy example, assume we're given a sequence of links.
因此，让我在玩具示例中进行说明，假设我们给出了一系列链接。
Five consistent of five integers, eight four two five and two.
五个一致的五个整数，八个四个二五个和两个。
So we start just by finding one of the minimum elements in this array, in this case it is two.
所以我们开始只是找到这个数组中的一个最小元素，在这种情况下它是两个。
Now lets just do the following, lets just swap it with the first element of our array.
现在让我们执行以下操作，让我们只使用数组的第一个元素进行交换。
After swapping, two stays in its final position, so two is the minimum value of our array and it is already in its first position.
交换后，两个停留在最终位置，因此两个是我们阵列的最小值，它已经处于第一个位置。
Now let's do the fun one, let's just forget about this element.
现在让我们做一个有趣的事情，让我们忘掉这个元素吧。
It is already in its final position and let's repeat the same procedure was the remaining part of our array.
它已经处于最终位置，让我们重复相同的过程是我们阵列的剩余部分。
Namely, we began first find the minimum value, it is again two.
也就是说，我们开始先找到最小值，它又是两个。
We'll swap it with the first element of the remaining part and then we'll just forget about this element.
我们将它与剩下部分的第一个元素交换，然后我们将忘记这个元素。
So again, we find the minimum value which is now four with what was the first element of the remaining part which is now the sole element of our array.
再次，我们找到最小值，现在是4，剩下部分的第一个元素是现在我们数组的唯一元素。
And then, we just forget about first three elements and we continue with only remaining parts.
然后，我们忘记了前三个元素，我们只继续剩下的部分。
So once again, we just keep growing the sorted part of our array.
所以再一次，我们只是继续增长数组的排序部分。
In the end, what we have, is that the whole array is sorted.
最后，我们得到的是整个数组的排序。
The pseudocode shown here on the slide, directly implements the idea of the selection sort algorithm that we just discussed.
幻灯片上显示的伪代码直接实现了我们刚才讨论的选择排序算法的想法。
So here we have a loop where i ranges from 1 to n.
所以这里我们有一个循环，其中i的范围从1到n。
Initially, i is equal to 1.
最初，我等于1。
Inside this loop, we compute the index of a minimal value in the array, from, within the list from i to n.
在这个循环中，我们计算数组中最小值的索引，从i到n的列表中。
We do this as follows, so we create a variable, minlndex which is initially equal to i.
我们这样做，所以我们创建一个变量minlndex，它最初等于i。
And then we go through all the remaining elements inside this part, I mean through elements from i + 1 to n.
然后我们浏览这部分内的所有剩余元素，我的意思是从i + 1到n的元素。
And if we find a smaller element we update the variable minlndex.
如果我们找到一个更小的元素，我们更新变量minlndex。
So in the end of this for loop, what we have is that minindex is a position of a minimal element inside the array from i to m.
所以在这个for循环的最后，我们得到的是minindex是从i到m的数组内最小元素的位置。
Then we swap this element with the element Ai.
然后我们将这个元素与元素Ai交换。
Namely, when i is equal to one, what we've done, we've found the minimal element in the well array and we've swapped it with the first element.
也就是说，当i等于1时，我们已经完成了，我们在井数组中找到了最小元素，并且我们已经将它与第一个元素交换。
So now, the first element of our array is in its final position.
所以现在，我们数组的第一个元素处于最终位置。
Then under second iteration of our loop, we do the same actually.
然后在循环的第二次迭代中，我们实际上做了同样的事情。
We find the minimum value, the position of a minimum value inside the remaining part of our array and put it on the second place.
我们找到最小值，在我们的数组的剩余部分内的最小值的位置，并把它放在第二位。
On the sort loop we find the minimum value in this remaining part and put it on the place and so on.
在排序循环中，我们找到剩余部分中的最小值并将其放在该位置，依此类推。
So we keep growing the sorted part of our array.
所以我们继续增长数组的排序部分。
So when it would be useful to check the online visualization to see how it goes, so let's do this.
因此，当检查在线可视化以查看它是如何运行时，请执行此操作。
This visualization shows how selection sort algorithm performs on a few different datasets.
此可视化显示了选择排序算法如何在几个不同的数据集上执行。
Namely on the random datasets, on a sequence which is nearly sorted.
即在随机数据集上，在几乎排序的序列上。
Also on a sequence which is sorted in reversed order.
也在按顺序排序的序列上。
And on a sequence which contains just a few unique elements.
并且在一个只包含一些独特元素的序列中。
So let's run this algorithm and see what happens.
那么让我们运行这个算法，看看会发生什么。
So you can see that indeed this algorithm just grows the sorted region, the sorted initial region of our array.
所以你可以看到，这个算法确实只是增长了排序区域，即数组的排序初始区域。
So another interesting property is it is revealed by this visualization is the following.
因此，另一个有趣的特性是通过这种可视化揭示了以下内容。
So the running time of this algorithm actually does not depend on input data.
因此，该算法的运行时间实际上并不依赖于输入数据。
So it only depends on the size of our initial sequence.
所以它只取决于我们的初始序列的大小。
The other [INAUDIBLE] time of how algorithm is quadratic and this is not difficult to see right? So what we have is two nested loops.
算法是二次方的其他[听不清]时间，这不难看出来吗？所以我们有两个嵌套循环。
In the outer loop, i ranges from 1 to n.
在外环中，i的范围从1到n。
In the inner loop, j ranges from i plus 1 to n, to find a minimum inside the remaining part of our array.
在内部循环中，j的范围从i加1到n，以在数组的剩余部分内找到最小值。
So in total we have quadratic number of iterations.
所以我们总共有二次迭代次数。
At this point however, we should ask ourselves whether our estimate was right in time of the selection, so our algorithm was too pessimistic.
然而，在这一点上，我们应该问自己我们的估计是否在选择时是正确的，所以我们的算法过于悲观。
And this is whar I mean by this.
这就是我的意思。
So recall that we have two nested loops.
所以请记住，我们有两个嵌套循环。
In the outer loop, i ranges from 1 to n.
在外环中，i的范围从1到n。
In the inner loop, g ranges from i + 1 to n.
在内环中，g的范围从i + 1到n。
So when i is equal to 1, the number of iterations of the inner loop is n- 1.
因此，当i等于1时，内循环的迭代次数为n-1。
However, when i is equal to 2, the number of iterations of the inner loop is n- 2, and so on.
但是，当i等于2时，内循环的迭代次数为n-2，依此类推。
So when i increases, the number of iterations of the inner loop decreases.
因此，当我增加时，内循环的迭代次数减少。
So a more accurate estimate for the total number of iterations of the inner loop would be the following, (n- 1) + (n- 2) + (n- 3) and so on.
因此，对内循环的总迭代次数的更准确估计将是以下，（n-1）+（n-2）+（n-3）等等。
So it is definitely less than n-squared.
所以肯定不到n平方。
However we will show this it is equal to n-squared.
但是我们会证明它等于n平方。
Namely, this is xx n-squared, and this it is roughly equaled n-square divided by two.
即，这是xx n平方，并且它大致等于n平方除以2。
The sum is that we need to estimate is called an Arithmetic Series, and there is a known formula for this for this sum.
总和是我们需要估计的称为算术系列，并且这个总和有一个已知的公式。
Namely 1 + 2 + 3 +, and so on, n, is equal to n(n+1)/2.
即1 + 2 + 3 +，依此类推，n等于n（n + 1）/ 2。
And this is how we can prove this formula.
这就是我们如何证明这个公式。
Let's just try it, all our n integers in a row, 1, 2, and so on, n.
让我们尝试一下，我们所有的n个整数连续，1,2，依此类推，n。
Below them let's write the same set of integers, but in the reverse order.
在它们下面让我们写相同的整数集，但顺序相反。
So, n, then n minus 1, and so on, 2, and 1.
那么，n，然后n减1，依此类推，2和1。
Then what we get is a row of size 2 by n.
然后我们得到的是一行大小为2的n。
Having n columns, and in each column, the sum of the corresponding two integers is equal to n plus 1.
具有n列，并且在每列中，相应的两个整数的总和等于n加1。
Great, so in the first column we have n and one, and in the second column we have two and minus one and so on and in the last column we have n and one.
太好了，所以在第一列中我们有n和一个，在第二列中我们有两个和减一个，依此类推，在最后一列我们有n和一个。
So the sum in each column is equal to n plus one and zero n columns.
因此每列中的总和等于n加1和0 n列。
Which means that the sum of all the numbers in our table is equal to n, when supplied by n plus one.
这意味着当由n加1提供时，表中所有数字的总和等于n。
So since this table contains our sum, the sum of the integers from 1 to n twice, we conclude that the sum of all the numbers from 1 to n is equal to n(n+1)/2.
因此，由于此表包含我们的和，即从1到n两次的整数之和，我们得出结论，从1到n的所有数字的总和等于n（n + 1）/ 2。
Another possibility to find this formula, to see why this formula is correct is to take a rectangle of size n, of dimensions n multiplied by n plus 1.
另一种找到这个公式的可能性，看看为什么这个公式是正确的是采用尺寸为n的矩形，其尺寸为n乘以n加1。
So it's area is equal to n multiplied by n plus one.
所以它的面积等于n乘以n加1。
And to cut it into two parts such as it's shown in the slide, such as the area of each of these two parts is equal to 1 + 2 + and so on n.
并将其切割成两部分，如幻灯片中所示，例如这两部分中的每一部分的面积等于1 + 2 +等等。
We're all ready to conclude.
我们都准备好结束了。
So we've just discussed the selection sort algorithm.
所以我们刚刚讨论了选择排序算法。
This algorithm is easy to implement, easy to analyze, and it's running time is n squared, where n is the size of the input sequence.
该算法易于实现，易于分析，运行时间为n平方，其中n为输入序列的大小。
So it sorts the input sequence and array in place.
因此它将输入序列和数组排序到位。
Meaning that it requires almost no extra memory.
这意味着它几乎不需要额外的内存。
I mean, all extra memory which is required by this algorithm is only for storing indices, like i, j and m index.
我的意思是，此算法所需的所有额外内存仅用于存储索引，如i，j和m索引。
There are many other quadratic algorithms, like insertion sort and bubble sort.
还有许多其他二次算法，如插入排序和冒泡排序。
We're not going to cover them here, and instead, in the next video we will proceed, to do a faster, a faster sort algorithm.
我们不打算在这里介绍它们，相反，在下一个视频中我们将继续，做一个更快，更快的排序算法。
------------- 40 -------------
03合并排序
In this video, we will study the so-called merge sort algorithm.
在本视频中，我们将研究所谓的合并排序算法。
It is based on the divide and conquer technique, which main idea is the following.
它基于分而治之的技术，其主要思想如下。
To solve a given computational problem, you first split it into two or more disjoint subproblems, then you solve each of these subproblems recursively.
要解决给定的计算问题，首先将其拆分为两个或更多不相交的子问题，然后递归地解决每个子问题。
And finally, you combine the results that you get from the recursive calls to get the result for your initial subproblem.
最后，您将从递归调用中获得的结果组合起来，以获得初始子问题的结果。
And this is exactly what we're going to do in merge sort algorithm.
这正是我们在合并排序算法中要做的事情。
So let's show a toy example.
所以让我们展示一个玩具示例。
We're given an array of size eight, and we are going to sort it.
我们给出了一个大小为8的数组，我们将对它进行排序。
First, we just split this array into two halves of size four, just the left half and the right half.
首先，我们将这个阵列分成四个大小的两半，只是左半部分和右半部分。
Then we make two recursive calls to sort both these parts.
然后我们进行两次递归调用来对这两部分进行排序。
These are two results in arrays.
这些是数组中的两个结果。
Now what remains to be done is to merge these two arrays into one, these two arrays of size four into one array of size eight.
现在还有待完成的是将这两个数组合并为一个，这两个大小为4的数组合并为一个大小为8的数组。
Well, let's think how this can be done.
那么，让我们想想如何做到这一点。
First of all, I claim that it is easy to find the minimal value in the resulting array.
首先，我声称在结果数组中很容易找到最小值。
Indeed, we know that the minimum value in this case in the first array is two, and the minimum value in the second array is one.
实际上，我们知道第一个数组中这种情况下的最小值是2，第二个数组中的最小值是1。
Which means that the minimum value in the result in merge array must be one.
这意味着合并数组中结果的最小值必须为1。
So let's take one from the right side of array, put it in the resulting array and forget about it.
所以让我们从数组的右侧取一个，将它放在结果数组中并忘记它。
It is already in its right place.
它已经在正确的位置。
What remains is an array of size four and an array of size three that still need to be merged.
剩下的是一个大小为4的数组和一个大小为3的数组，仍然需要合并。
Well, again, it is easy to find the minimum value of the result of merging these two arrays.
那么，再次，很容易找到合并这两个数组的结果的最小值。
In this case, it is two, because the minimum value in the array of size four is two, and the minimum value in the arrays of size three is six.
在这种情况下，它是两个，因为大小为4的数组中的最小值是2，而大小为3的数组中的最小值是6。
So two is smaller than six, so we get two out of our left array, put it into the resulting array after one, and press hit.
所以两个小于六个，所以我们从左侧数组得到两个，在一个之后将它放入结果数组中，然后按下命中。
In the end, we get the following sorted array.
最后，我们得到以下排序数组。
Again, the pseudocode of the merge sort algorithm directly implements this idea.
同样，合并排序算法的伪代码直接实现了这个想法。
So this pseudocode takes an input array A of size n as an input.
因此，该伪代码将大小为n的输入数组A作为输入。
And if n is equal to 1, then in this case, just nothing needs to be done, we can just return the rate A itself.
如果n等于1，那么在这种情况下，只需要做任何事情，我们就可以返回速率A本身。
If n is greater than 1, on the other hand, then we split the rate A into two roughly equal parts and sort them recursively.
另一方面，如果n大于1，那么我们将速率A分成两个大致相等的部分并递归地对它们进行排序。
We call them B and C here.
我们在这里称他们为B和C.
Then the only thing that needs to be done is to merge these two sorted arrays.
然后，唯一需要做的就是合并这两个排序的数组。
So this is done in the procedure merge, which we will present on the next slide.
所以这是在过程合并中完成的，我们将在下一张幻灯片中介绍。
And finally, we just return the result of this merging procedure.
最后，我们只返回此合并过程的结果。
The pseudocode of the merging procedure is also straightforward.
合并过程的伪代码也很简单。
Assumes that we are given two sorted arrays, B and C, of size p and q respectively, and we would like to merge them into a sorted array of size p + q.
假设我们给出了两个分别为大小为p和q的排序数组B和C，我们希望将它们合并为一个大小为p + q的排序数组。
So the first thing we do is create an array of size p + q in array D.
所以我们要做的第一件事是在数组D中创建一个大小为p + q的数组。
It is initially empty.
它最初是空的。
Then we keep doing the following thing.
然后我们继续做以下事情。
So what is the minimum value among all the values stored in the arrays B and C? Well, it is easy to find.
那么存储在数组B和C中的所有值中的最小值是多少？嗯，很容易找到。
We know that the first element in the array B is its smallest element, and the first element in the array C is its smallest element.
我们知道数组B中的第一个元素是它的最小元素，而数组C中的第一个元素是它的最小元素。
So the smallest one among these two is the smallest element inside the unit of these two arrays.
因此，这两者中最小的一个是这两个阵列单元内的最小元素。
So we just find the minimum of these first elements and move it from one of these arrays to the results in array D, and forget about this element completely.
所以我们只找到这些第一个元素的最小值，并将它从这些数组中的一个移到数组D中的结果，并完全忘记这个元素。
Now what is left is essentially the same problem.
现在剩下的就是同样的问题。
We're left with two sorted arrays, and we still need to merge them.
我们留下了两个排序的数组，我们仍然需要合并它们。
So we do it exactly the same.
所以我们完全一样。
We take the first two elements, we compare them and move the smaller one to the resulting array.
我们采用前两个元素，我们比较它们并将较小的元素移动到结果数组中。
And we keep doing this while both of these arrays are empty.
我们继续这样做，而这两个数组都是空的。
I mean, we need this to be able to take their first elements.
我的意思是，我们需要这个能够采取他们的第一个元素。
When one of them becomes empty, we just copy the rest of the other array to the resulting array D.
当其中一个变空时，我们只将其他数组的其余部分复制到结果数组D.
I mean, where rest to the resulting array D.
我的意思是，休息到结果数组D.
Well, it is not difficult to see that this procedure is correct, and the trying time is p + q, namely, the size of the array p plus the size of the array q.
嗯，不难看出这个程序是正确的，并且尝试时间是p + q，即数组p的大小加上数组q的大小。
And this just because we just can both of these arrays from left to right in the run of this merging procedure.
这只是因为我们只是在这个合并过程的运行中从左到右都可以使用这两个数组。
This is how sorting our initial array of size eight by the merge sort algorithm looks like.
这是通过合并排序算法对大小为8的初始数组进行排序的方式。
So the merge sort algorithm first splits the initial array of size eight into two arrays of size four.
因此，合并排序算法首先将大小为8的初始数组拆分为两个大小为4的数组。
Each of these arrays of size four in turn is split into two arrays of size two, and each of them is split into two arrays of size one.
这些大小为4的数组中的每一个依次被分成两个大小为2的数组，并且每个数组被分成两个大小为1的数组。
Then merge procedure starts merging these arrays of size one into arrays of size twos and into, then these arrays of size two into a size four.
然后合并过程开始将这些大小为1的数组合并为大小为twos的数组，然后将这些大小为2的数组合并为4。
And finally, it merges the result into arrays of size four, into the resulting array of size eight.
最后，它将结果合并到大小为4的数组中，并将其合并到大小为8的结果数组中。
We are now going to prove that the running time of the merge sort algorithm, on a sequence containing n elements, is big O of n log n.
我们现在要证明合并排序算法在包含n个元素的序列上的运行时间是n log n的大O.
Know that this is significantly faster than a quadratic selection sort algorithm.
知道这比二次选择排序算法快得多。
For example, it is perfectly okay to sort the sequence of size 1 million, for example, 10 to the 6th, on your laptop using merge sort algorithm.
例如，使用合并排序算法在笔记本电脑上排序大小为100万的序列（例如10到6）是完全可以的。
While for the quadratic time selection sort algorithm, sorting a sequence of size 10 to the 6th, 1 million, will take roughly 10 to the 12th operations, which is too much for modern computers.
而对于二次时间选择排序算法，将大小为10的序列排序到第6,100万，大约需要10到12次操作，这对于现代计算机来说太过分了。
Okay, so to prove this lemma, to prove the upper bound on the running time of the merge sort algorithm, first know that to merge two parts of size n over 2 of our initial array, takes the linear time.
好的，为了证明这个引理，为了证明合并排序算法运行时间的上限，首先要知道在我们的初始数组中合并两个大小为n的部分，需要线性时间。
Namely, big O of n, because while the left part has size n over 2, the right part has size n over 2.
即，n的大O，因为左边部分的尺寸n大于2，右边部分的尺寸n大于2。
And for merging, we basically just combo these parts from left to right.
对于合并，我们基本上只是从左到右组合这些部分。
So it takes just a linear amount of work to do this.
因此，这需要一定量的工作量。
Which, in turn means, that if we denote by T of n the running time of our merge sort algorithm, then it satisfies the following recurrence.
反过来意味着，如果我们用n表示我们的合并排序算法的运行时间，则它满足以下重复。
T(n) is at most 2T(n / 2) + big O(n).
T（n）至多为2T（n / 2）+大O（n）。
Here 2T(n / 2) could response to two recursive calls.
这里2T（n / 2）可以响应两个递归调用。
So we denote it by T(n), the running time of our algorithm on input of size n.
所以我们用T（n）来表示它，我们的算法在大小为n的输入上的运行时间。
So when we sort two sequences of size n / 2, we spend time twice T(n / 2).
因此，当我们对两个大小为n / 2的序列进行排序时，我们花费时间两次T（n / 2）。
So the big O of n term corresponds to what we do before we make recursive calls and what we do after recursive calls.
所以n项的大O对应于我们在进行递归调用之前所做的事情以及我们在递归调用之后所做的事情。
So what we do before is just split the input array into two halves.
所以我们之前做的只是将输入数组分成两半。
What we do after is merging the results of two arrays into one array of size n.
我们所做的是将两个数组的结果合并为一个大小为n的数组。
So it is not difficult to see that all of this can be done in linear time.
因此，不难看出所有这些都可以在线性时间内完成。
So we get this recurrence, and on the next slide, we're going to show that this recurrence implies that the running time of our algorithm is bounded from above by n log n.
所以我们得到了这种复发，在下一张幻灯片中，我们将证明这种复发意味着我们的算法的运行时间从上面开始被n log n限制。
To estimate the running time of this algorithm, let's consider its recursion tree.
为了估计这个算法的运行时间，让我们考虑它的递归树。
Namely, at the top of this tree, we have one array of size n.
也就是说，在这棵树的顶部，我们有一个大小为n的数组。
So for this array of size n, we make two recursive calls for arrays of size n over 2.
因此对于这个大小为n的数组，我们对大小为n超过2的数组进行两次递归调用。
Each of these arrays of size n over 2 in turn is split into two arrays of size n over 4.
这些大小为n超过2的阵列中的每一个依次被分成两个大小为n超过4的阵列。
So we get four arrays of size of n over 4 and so on.
所以我们得到四个大小为n的数组超过4，依此类推。
So in this tree, we have log n levels.
所以在这棵树中，我们有log n级。
Now let's estimate the work done at each of the levels of these three separately, namely, once again, to solve a problem of size n.
现在让我们分别估算这三个级别中的每个级别所做的工作，即再次解决大小为n的问题。
To sort an array of size n, we first prepare to make recursive calls.
要对大小为n的数组进行排序，我们首先准备进行递归调用。
In this case, we just split the array into two halves of size n over 2.
在这种情况下，我们只是将数组拆分为两个大小为n的两半。
Then we do make recursive calls, and then we need to combine the results.
然后我们做了递归调用，然后我们需要结合结果。
So all the work now inside recursive calls will be accounted for on the lower levels of this tree.
因此，现在递归调用内的所有工作都将在此树的较低级别进行说明。
So now what we are going to do is to account for only the work done before the recursive calls and after the recursive calls at each separate level.
所以现在我们要做的是只考虑递归调用之前和每个单独级别的递归调用之后完成的工作。
And we know already that it takes linear time to do this.
我们已经知道这需要线性时间。
I mean, if we have an array of size n, it takes linear time to split it into two halves.
我的意思是，如果我们有一个大小为n的数组，则需要线性时间将其分成两半。
And then it takes linear time to combine the results of recursive calls into one array.
然后需要线性时间将递归调用的结果组合到一个数组中。
So let's just denote this time by cn, I mean let's denote the hidden constant inside big O by c.
所以让我们用cn表示这个时间，我的意思是让我们用c来表示大O中隐藏的常数。
Then what we can say is that on the top level we spend time cn.
那么我们可以说的是，在顶级我们花费时间cn。
Then on the next level, for each subarray, we spend time c times n over 2, because the size of array is n over 2.
然后在下一个级别上，对于每个子阵列，我们花费时间c乘以n超过2，因为数组的大小是n超过2。
However, we have 2 arrays, so the total work that we do at this level is 2 multiplied by c, multiplied by n over 2, which is again just cn.
但是，我们有2个数组，所以我们在这个级别做的总工作是2乘以c，乘以n超过2，这也只是cn。
On the next level, we spend time 4 because we have 4 arrays multiplied by c, multiplied by n over 4, because the size of the array is now n over 4.
在下一个级别，我们花费时间4因为我们有4个数组乘以c，乘以n超过4，因为数组的大小现在是n超过4。
This is a cn again, and so on.
这又是一个cn，依此类推。
So we have log n levels.
所以我们有log n级别。
At each level, we do roughly cn operations.
在每个级别，我们都进行大致的操作。
So the total number of operations in our algorithm is cn log n, which proves our lemma.
因此，我们算法中的操作总数是cn log n，这证明了我们的引理。
So again, what we've just proved is that the running time of the merge sort algorithm is big O of n log n.
再说一遍，我们刚刚证明的是合并排序算法的运行时间是n log n的大O.
So in the next video, we will show that actually no algorithm, no comparison based algorithms, to be completely formal, can sort a given sequence of n elements asymptotically faster than in n log n time.
所以在下一个视频中，我们将展示实际上没有算法，没有基于比较的算法，完全正式，可以对n个元素的给定序列进行排序，比n log n时间更快。
Which actually means that the merge sort algorithm is asymptotically optimal.
这实际上意味着合并排序算法是渐近最优的。
------------- 41 -------------
04基于比较的排序下限
In the previous video, we proved that the running time of the Warshall algorithm on a sequence consisting of n elements is big log of n.
在前面的视频中，我们证明了Warshall算法在由n个元素组成的序列上的运行时间是n的大对数。
In this video we will show that this bond is essentially optimal.
在这个视频中，我们将证明这种联系基本上是最佳的。
We will do this by showing that any correct sorting algorithm that sorts an object by comparing pairs of them.
我们将通过显示任何正确的排序算法来做到这一点，该算法通过比较对象来对对象进行排序。
Must make a clear stand log in operation such as particularly in the worst case.
必须明确登记操作，特别是在最坏的情况下。
Once again we say that the sorting algorithm is comparison based if it sorts the given objects just by comparing pairs of them.
我们再一次说排序算法是基于比较的，如果它只是通过比较它们的对来对给定对象进行排序。
We can imagine the following situation, we have add objects, that look the same, for example in walls, but have different weights.
我们可以想象以下情况，我们添加了看起来相同的对象，例如在墙壁中，但具有不同的权重。
And we also have pen balance.
我们还有笔平衡。
And this pen balance is, our only way to compare pairs of these balls.
而这笔平衡是我们比较这些球的唯一方法。
And our goal is to rearrange these balls, in order of increasing weights.
我们的目标是按重量增加的顺序重新排列这些球。
So, for example, the two source and algorithms that we'll already consider it, namely the selection sort algorithm and the merge sort algorithm are both comparison based algorithms.
因此，例如，我们已经考虑过的两个源和算法，即选择排序算法和合并排序算法都是基于比较的算法。
So for example, the selection sort algorithm at each region finds the minimum value in the remaining part of the array.
因此，例如，每个区域的选择排序算法在数组的剩余部分中找到最小值。
And it does so exactly by comparing pairs of objects, right? Also, the merge sort algorithm is also comparison based algorithm.
它通过比较对象来完全这样做，对吗？此外，合并排序算法也是基于比较的算法。
So it first splits an array into halves.
所以它首先将一个数组分成两半。
And then it needs to merge the two results in arrays.
然后它需要将两个结果合并到数组中。
And when merging the results in arrays, it also uses comparisons, right? So we take the first two elements of two sorted arrays.
当将结果合并到数组中时，它也会使用比较，对吗？所以我们采用两个排序数组的前两个元素。
We compare them, and based on this comparison we take one of these elements out of one of those two arrays and put it to the result in the array.
我们比较它们，并根据这个比较，我们从这两个数组中的一个中取出其中一个元素，并将它放到数组中的结果中。
So this as a formal statement that we're going to prove.
所以这是我们要证明的正式声明。
It says that any comparison based algorithm that sorts an object has running time.
它说任何对对象进行排序的基于比较的算法都有运行时间。
At least big and n log n in the worst case.
在最坏的情况下至少大和n log n。
So but in otherwise we can say the following.
所以，否则我们可以说以下内容。
Assume that you have an algorithm that sorts an object by comparing pairs of them.
假设您有一个算法可以通过比较对象来对对象进行排序。
It can be the case that for some given both sequences of an object, your algorithm performs less than analog operations.
可能的情况是，对于给定对象的两个序列，您的算法执行的操作少于模拟操作。
Say, linear number of operations.
比方说，线性运算数。
However, it cannot be the case that your algorithm always sorts in time, asymptotically less than n log n.
但是，不可能的是，您的算法总是按时间排序，渐近地小于n log n。
Meaning that, there must exist, sequence of objects, on which your algorithm will perform at least performing a login comparison to sort such sequences.
这意味着，必须存在，对象序列，您的算法将在其上执行，至少执行登录比较以对这些序列进行排序。
Any comparison based algorithm can be shown as a huge tree that contains all possible sequences of comparisons that can be made by this algorithm.
任何基于比较的算法都可以显示为一个巨大的树，其中包含可以通过此算法进行的所有可能的比较序列。
For example, here on the slide.
例如，在幻灯片上。
We show a simple algorithm that sort three object.
我们展示了一个简单的算法，它排序三个对象
Three objects.
三个对象。
So it starts by comparing a1 and a2.
所以它首先比较a1和a2。
If a1 happens to be smaller than a2, then we proceed to comparing a2 and a3.
如果a1碰巧小于a2，那么我们继续比较a2和a3。
If a2 is smaller than a3, then we already know the permutation of the input three objects in non-decreasing order.
如果a2小于a3，那么我们已经知道输入三个对象的非排列顺序的排列。
Namely, we know that a1 is smaller than a2, and we know that a2 is smaller than a3.
也就是说，我们知道a1小于a2，我们知道a2小于a3。
So we can just output the following permutation.
所以我们可以输出以下排列。
Right.
对。
If on the other hand, a2 happened to be at least a3, then at this point we already know that a2 is greater than a1.
另一方面，如果a2碰巧至少是a3，那么此时我们已经知道a2大于a1。
And a2 Is no smaller than a3.
而且a2不小于a3。
So at this point, we know that a2 is the maximum element among our three elements.
所以在这一点上，我们知道a2是我们三个元素中的最大元素。
However, we still need to compare a1 and a3, so we do this comparison, and based on its result, we output either this permutation or this permutation.
但是，我们仍然需要比较a1和a3，所以我们进行这种比较，并根据其结果输出这种排列或这种排列。
Well this was the case when a1 happened to be small as an a2.
那么当a1恰好小到a2时就是这种情况。
However we need also to consider the case when a1 happened to be at least a2.
但是，我们还需要考虑a1恰好至少为a2的情况。
So we proceed similarly in this case.
所以我们在这种情况下也是如此。
So this is just a toy example for an algorithm for a comparison based algorithm comparing three objects, sorting three objects.
因此，这只是一个算法的玩具示例，用于基于比较的算法比较三个对象，对三个对象进行排序。
However, such a huge tree can be drawn for any comparison based health algorithm.
但是，可以为任何基于比较的健康算法绘制这样一棵巨大的树。
So at the root of this tree we have the first comparison.
所以在这棵树的根部我们进行了第一次比较。
And its children will label just the next comparison that is made based on the result of the first comparison and so on.
它的孩子将根据第一次比较的结果标记下一次比较，依此类推。
So each internal node is labeled with some comparison.
因此，每个内部节点都标有一些比较。
And each leaf is labeled with a permutation of m input objects.
每个叶子都标有m个输入对象的排列。
A simple but crucial for this argument observation is that in this tree, we must have at least n factorial leaves.
对于这个论证观察来说，一个简单但至关重要的是，在这棵树中，我们必须至少有n个阶乘叶。
And this is because we have n factorial different permutations of n input objects.
这是因为我们有n个因子不同的n个输入对象的排列。
Where n factorial is defined to be the product of n and minus one and minus two and so on.
其中n阶乘被定义为n和减1和减2的乘积，依此类推。
So why is that? Why we must have any possible permutation as a leaf in our tree? Well, this is just because it is possible that this permutation is a lead output, is the right output of our algorithm.
那为什么呢？为什么我们必须在树上留下任何可能的排列？嗯，这只是因为这个排列可能是一个前导输出，是我们算法的正确输出。
So for example on our previous slide, on our toy example, we have three objects and there are six possible permutations of these three objects, and there are six leaves in our tree.
例如，在我们之前的幻灯片中，在我们的玩具示例中，我们有三个对象，这三个对象有六种可能的排列，我们的树中有六个叶子。
For example one of them is 213 and it says that the second element is the smallest one, then goes the first element, and then goes the third element.
例如，其中一个是213，它表示第二个元素是最小的元素，然后是第一个元素，然后是第三个元素。
And indeed there are cases when this is the right answer.
事实确实，这是正确的答案。
Right? So when the input data consists of three objects, such that the second element is the smallest one, the first one is the next one, and the third element is the largest one.
对？因此，当输入数据由三个对象组成时，第二个元素是最小的一个，第一个是下一个，第三个元素是最大的一个。
Right? So once again, you have a huge tree which carries a comparison based algorithm.
对？再一次，你有一棵巨大的树，它带有一个基于比较的算法。
There must be at least n factorial leaves, because each possible permutation must be present as a leaf in our tree.
必须至少有n个阶乘叶，因为每个可能的排列必须作为我们树中的叶子存在。
So on the other hand the maximal number of comparisons made by our algorithm corresponds to the depths of our tree.
因此，另一方面，我们的算法所做的最大比较次数对应于树的深度。
So the depths is defined as the maximal number of edges run away from the root to the leaf, to some leaf of our tree.
所以深度定义为从根到叶子的最大边数，到树的一些叶子。
So and this is exactly the maximal possible number of comparisons which our algorithm makes.
所以，这正是我们的算法所做的最大可能的比较次数。
So now we would like to show that d must be large in our case, must be at least be big O omega of analog n.
所以现在我们想表明在我们的情况下d必须很大，必须至少是模拟n的大O oga。
And we know already that our tree contains many, many leaves.
我们已经知道我们的树上有很多很多叶子。
Mean n factorial is a function that grows extremely fast.
平均n阶乘是一种非常快速增长的函数。
Okay so, intuitively we would like to show that if a tree has many, many leaves, then it has a large depth.
好的，直觉上我们想表明，如果一棵树有很多很多叶子，那么它有很大的深度。
And at least intuitively this clear.
至少在直觉上这清楚了。
If you have a tree of very small depths then it must just a few leaves, right? But, we know that it has many, many, many leaves, in fact at least ten factorial leaves.
如果你有一棵非常小的树，那么它必须只有几片叶子，对吧？但是，我们知道它有许多很多叶子，实际上至少有十个叶子叶。
To formally show this we need the following, we need the following estimate.
为了正式表明我们需要以下内容，我们需要以下估计。
The depths of a binary tree is at least a binary algorithm of its number of leaves or equivalently 2 to the depths is at least its number of leaves.
二叉树的深度至少是其叶数的二进制算法，或等效于深度的2至少是其叶数。
Well this can be proved formally, but let me just show you this informally.
嗯，这可以正式证明，但让我非正式地告诉你。
Let's concede a tree for example of depth 1.
让我们承认一棵树，例如深度1。
So in this case, d is equal to 1.
所以在这种情况下，d等于1。
And it is clear that the maximal possible number of leaves in a tree of depth 1 is equal to 2.
并且很明显，深度为1的树中叶子的最大可能数量等于2。
So now, let's try to understand what is the maximal possible number of leaves in a depth of In a tree of depth 2.
所以现在，让我们试着了解在深度为2的树深度中叶子的最大可能数量。
For example, this is a tree of depth 2.
例如，这是深度为2的树。
This is another tree of depth 2, it has has three leaves.
这是另一棵深度为2的树，它有三片叶子。
And this is a tree of depth 2 that has maximal possible number of leaves, in this case it is 4.
这是一棵深度为2的树，其叶子数量最多，在这种情况下为4。
It is 2 to the d indeed.
它确实是2。
And intuitively it is clear that to have a tree of depth d that has maximal possible number of leaves.
并且直观地显示具有最大可能叶数的深度为d的树。
We need to take a tree which has a full binary tree of depth d, right? And this tree has exactly 2 to the d leaves.
我们需要一棵树有一个深度为d的完整二叉树，对吧？而这棵树正好有2片叶子。
So the maximal number of leaves in a tree of depth d is 2 to the d.
因此深度为d的树中叶子的最大数量是d的2。
Which proves that 2 to the d is at least l.
这证明2到d至少是l。
Okay, so the last step that we need to show is that if we have n factorial leaves, then the depths of our tree is at least big log n again.
好的，所以我们需要展示的最后一步是，如果我们有n个阶乘叶子，那么我们树的深度至少是大log n。
And we will show this on the next slide.
我们将在下一张幻灯片中展示这一点。
It remains to estimate log of n factorial.
它仍然是估计n阶乘的对数。
We're going to show here that log of n factorial is at least c times n log n.
我们将在这里显示n因子的对数至少是n次n log n。
Which means as it works that log of n factorial is big log of n log n.
这意味着n因子的日志是n log n的大对数。
To do this, we express n factorial as a product of 1, 2, 3.
为此，我们将n阶乘表示为1,2,3的乘积。
And so on n minus 1, and then right algorithm of product of these numbers as a sum of their algorithm.
等等n减1，然后将这些数的乘积算法作为算法的总和。
So, log of n factorial is equal to log of 1 plus log of 2 plus log of 3 and so on plus log of n.
因此，n阶乘的log等于1的log加2的log加上3的log而依此类推n的log。
So, this is a sum of an object.
所以，这是一个对象的总和。
Let's just throw away the first half of this and elements, and leave only the second half.
让我们扔掉这个和元素的前半部分，只剩下下半部分。
So in this second half, we have n over two elements and each of them is at least log of n over two, right? So this has algorithms of numbers which are at least n over two.
所以在下半场，我们有n个超过两个元素，每个元素至少是两个n的对数，对吗？因此，这具有至少n超过两的数字算法。
So we have n over two.
所以我们有两个以上。
Elements, each of them is at least algorithms of n over 2.
元素，每个元素至少是n超过2的算法。
This allows us to conclude that log sum is at least 10 over 2 times log of n over 2.
这使我们得出结论，对数总和至少是2倍于2的n的log。
And this in turn be big log of n for a simple reason.
而这又是n的大对数，原因很简单。
So log n over 2 is equal to log n minus 1.
因此log 2 over 2等于log n减1。
Well, this grows like log n, right? Because log n is a growing function and one is a constant so again minus one goes as log n.
嗯，这就像log n一样，对吗？因为log n是一个增长的函数，一个是常数，所以再减去一个作为log n。
And over grows as n, right? So, this is up to constant factors, this is just n.
过度增长为n，对吗？所以，这取决于常数因素，这只是n。
So, n over two times log n over two grows like n log n.
因此，n超过两次log n超过两次增长就像n log n。
Okay so this concludes our proof, and this concludes the proof of the fact that any comparison based algorithm must make at least n log n adorations in the worst case.
好的，所以这就结束了我们的证明，这就证明了这样一个事实的证据：任何基于比较的算法必须在最坏的情况下至少进行n log n次加工。
Once again, another conclusion is that when merged sort algorithms that we considered in the previous lecture e is asymmetrically optimal.
再一次，另一个结论是，当我们在前面的讲座e中考虑的合并排序算法是非对称最优的。
In the next video we will see an algorithm that actually sorts n given objects in time less than n log n.
在下一个视频中，我们将看到一种算法，该算法实际上对n个给定对象的时间小于n log n。
Actually in time just in linear time.
实际上只是在线性时间。
In time big log of n however, it will sort the n given objects, knowing something about these objects.
然而，在n的时间大日志中，它将对n个给定对象进行排序，了解这些对象。
It will only sort the given objects if the subject has small integers.
如果主题具有小整数，它将仅对给定对象进行排序。
And we will sort them without actually comparing them to each other.
我们会对它们进行排序，而不是将它们相互比较。
------------- 42 -------------
05非基于比较的排序算法
In this last video we will show that there are cases when we can sort the n given objects without actually comparing them to each other.
在最后一个视频中，我们将展示有些情况，我们可以对n个给定对象进行排序，而无需实际将它们相互比较。
And for such algorithms, our lower bound with n log n does not apply.
对于此类算法，我们的n log n下限不适用。
Well, probably the most natural case when we can sort the n given objects without comparing them to each other is the case when our input sequence consists of small integers.
好吧，当我们输入序列由小整数组成时，我们可以对n个给定对象进行排序而不将它们相互比较，这可能是最自然的情况。
We will illustrate it with a toy example.
我们将用玩具示例来说明它。
So consider an array of size 12 which consists of just three different digits.
因此，考虑一个大小为12的数组，它只包含三个不同的数字。
I mean each element of our array is equal to either 1, 2 or 3.
我的意思是我们数组的每个元素都等于1,2或3。
Then we can do the following, let's just go through this array from left to right.
然后我们可以执行以下操作，让我们从左到右遍历这个数组。
I mean by a simple count and count the number of occurrences of 1, 2 and 3.
我的意思是通过一个简单的计数并计算出现次数为1,2和3。
Just by scanning this array you will find out that 1 appears two times, 2 appears seven times, and 3 appears three times.
只需扫描此阵列，您就会发现1出现两次，2次出现7次，3次出现3次。
And this information is enough for us to sort these objects, so we can use this information to fill in the resulting array, A prime.
这些信息足以让我们对这些对象进行排序，因此我们可以使用这些信息来填充结果数组A prime。

所以我们放1次，然后我们放2次7次，然后放3次3次。
And this gives us the resulting sorted array A prime, right? So what just happened is that we sorted this array, these n objects, without comparing these objects to each other.
这给了我们生成的排序数组A prime，对吗？所以刚刚发生的事情是我们对这个数组进行了排序，这些n个对象，而不是将这些对象相互比较。
We just counted the number of occurrences of each number, and for this we used, essentially, the information that this array contains small integers.
我们只计算了每个数字的出现次数，为此我们基本上使用了这个数组包含小整数的信息。
The algorithm that we just saw is called counting sort algorithm.
我们刚刚看到的算法称为计数排序算法。
Its main ideas are the following.
其主要思想如下。
I assume that we're given an array A of size n, and we know that all its elements are integers in the range from 1 to M.
我假设我们给出了一个大小为n的数组A，我们知道它的所有元素都是1到M范围内的整数。
Then, we do the following.
然后，我们执行以下操作。
We create an array count of size M, and by scanning the initial array A just once from left to right, we count the number of occurrences of each i from 1 to M, and we store this value in the cell count of i.
我们创建一个大小为M的数组计数，并且通过从左到右扫描初始数组A，我们计算每个i的出现次数从1到M，并将该值存储在i的单元数中。
So, we scan the array A from left to right, and whenever we see an element equal to i, we increment the value stored in the cell count of i.
因此，我们从左到右扫描数组A，每当我们看到一个等于i的元素时，我们增加存储在i的单元数中的值。
Then when this array is filled, we can use this information to fill in the resulting array A prime, as we did in our toy example.
然后，当填充此数组时，我们可以使用此信息来填充结果数组A prime，就像我们在玩具示例中所做的那样。
So this is a pseudocode of the count and sort algorithm.
所以这是计数和排序算法的伪代码。
Here we're given an array A of size M and we assume that all the elements of this array are integers from 1 to M.
这里我们给出了一个大小为M的数组A，我们假设这个数组的所有元素都是从1到M的整数。
So we introduce the recount of size M which is initially filled in by zeroes.
因此，我们引入了大小为M的重新计数，它最初用零填充。
Then by scanning our initial array we fill in this array.
然后通过扫描我们的初始数组，我们填写这个数组。
Namely, whenever we see an element k in our initial array, we increase the cell count of k.
也就是说，每当我们在初始数组中看到元素k时，我们就会增加k的单元数。
So after the first loop of this algorithm, we know exactly the total number of occurrences of each number k from 1 to M in our initial array.
因此，在该算法的第一个循环之后，我们确切地知道在我们的初始数组中每个数字k的出现总数从1到M.
So for example in our toy example two slides before, we counted that the number 1 appears two times in our initial array, the number 2 appears seven times in our initial array, and number 3 appears three times.
因此，例如在我们的玩具示例之前的两张幻灯片中，我们计算出数字1在我们的初始数组中出现两次，数字2在我们的初始数组中出现七次，而数字3出现三次。
So at this point, we know that in the resulting array, the first two elements will be occupied by the number 1, the next seven elements will be occupied by the number 2, and the next three elements will be occupied by the number 3.
所以在这一点上，我们知道在结果数组中，前两个元素将被数字1占用，接下来的七个元素将被数字2占用，接下来的三个元素将被数字3占用。
Now we would like, instead of having just the lengths of these three intervals, we would like to compute the starting point of each interval.
现在我们想要计算每个区间的起点，而不是只有这三个区间的长度。
So we do this in a new loop.
所以我们在一个新循环中这样做。
And for this we introduce a new array Pos.
为此我们引入了一个新的阵列Pos。
So Pos[1] is equal to 1, meaning that number 1 will occupy a range starting from the first index.
因此Pos [1]等于1，意味着数字1将占据从第一个索引开始的范围。
And the starting point for each subsequent range is computed as a starting point of each previous range, plus the length of this previous range.
并且每个后续范围的起点被计算为每个先前范围的起始点加上该先前范围的长度。
So Pos[j] is computed as Pos[j -1] + Count[j- 1].
所以Pos [j]被计算为Pos [j -1] + Count [j-1]。
So at this point we know the starting point for each range.
所以在这一点上我们知道每个范围的起点。
Namely, k in the resulting array, number k will occupy a range starting from Pos[k].
即，在结果数组中的k，数字k将占据从Pos [k]开始的范围。
Then we just count our initial array and whenever we see an element, we always know where to put it in the initial array.
然后我们只计算我们的初始数组，每当我们看到一个元素时，我们总是知道将它放在初始数组中的哪个位置。
So then let me remind you that we do not just fill in the array with numbers from 1 to M, but we copy elements from our initial array.
那么让我提醒你，我们不只是用1到M的数字填充数组，但是我们从初始数组中复制元素。
This is because what we are looking for in this certain problem is a permutation of our initial n given objects.
这是因为我们在这个特定问题中寻找的是我们最初的n个给定对象的排列。
Because what we have is probably not just number, not just integers from 1 to M, but these numbers are keys of some probably complex object.
因为我们所拥有的不仅仅是数字，而不仅仅是从1到M的整数，但这些数字可能是某些复杂对象的关键。
Okay, so the running time of this algorithm can be easily seen to be big O of M plus M.
好的，所以这个算法的运行时间很容易看出是M加M的大O.
This is just because here we have three loops.
这只是因为我们有三个循环。
So the first loop has n iterations, the second loop has M iterations, and the last loop also has n iterations.
所以第一个循环有n次迭代，第二个循环有M次迭代，最后一个循环也有n次迭代。
Well, so, this is the formal statement.
那么，这是正式的声明。
The running time of count and sort algorithm is just n + M.
计数和排序算法的运行时间仅为n + M.
And the final remark about this algorithm is that if M grows no faster than n, namely, for example, if our array is filled by integers from 1 to n, or if this array is filled just by integers which are upper bounded by some constant, then the running time of our count and sort algorithm is just linear in n.
关于这个算法的最后一点是，如果M的增长速度不快于n，即，例如，如果我们的数组由1到n的整数填充，或者如果这个数组只是被一些常数上限的整数填充，那么我们的计数和排序算法的运行时间在n中只是线性的。
I will now summarize the last three videos.
我现在将总结最后三个视频。
So we first covered the merge sort algorithm.
所以我们首先介绍了合并排序算法。
So this is a divide and conquer based algorithm that proceeds as follows.
因此，这是一种基于分而治之的算法，其过程如下。
Given an array of size n it first splits it into two halves, both roughly equal size, then it sorts them recursively and then it merges them into the resulting array.
给定一个大小为n的数组，它首先将它分成两半，两者大小大致相等，然后递归地对它们进行排序，然后将它们合并到结果数组中。
We then, and we showed that the running time of this algorithm is big O(n log n), which is quite fast actually.
然后，我们证明了这个算法的运行时间是大O（n log n），实际上非常快。
Almost teeny.
几乎是小孩子。
We then showed that no other comparison based algorithm can sort n given objects asymptotically faster than an n log n.
然后我们表明，没有其他基于比较的算法可以对n个给定对象进行排序，比n log n更快。

所以我们通过显示任何基于比较的算法必须区分太多的情况来做到这一点。
Between n factorial possible permutations.
在n个阶乘可能的排列之间。
For this, in the worst case, a comparison based algorithm must perform at least big O(n log n) interpolations.
为此，在最坏的情况下，基于比较的算法必须执行至少大的O（n log n）个插值。
We then showed that it can be actually done faster and in certain problems, can be solved in time less than n log n, in some cases.
然后我们表明它实际上可以更快地完成并且在某些问题中，在某些情况下可以在小于n log n的时间内解决。
For example, in the case when our input array contains small varied integers.
例如，在我们的输入数组包含小的变化整数的情况下。
------------- 43 -------------
01概述
Hello, and welcome to the next lesson in the Divide-and-Conquer model.
您好，欢迎来到Divide-and-Conquer模型的下一课。
This lesson is going to be devoted to the quick sort algorithm, which is one of the most efficient and commonly used in practice sorting algorithms.
本课将专门介绍快速排序算法，这是实践排序算法中最有效和最常用的算法之一。
Well, as usual, we start with the overview of this algorithm.
好吧，像往常一样，我们从这个算法的概述开始。
The algorithm is comparison based, meaning that it sorts the n given elements by comparing pairs of them.
该算法是基于比较的，这意味着它通过比较它们的对来对n个给定元素进行排序。
Its running time is also asymptotically n log n, but not in the worst case, as was with the merge sort algorithm, for example, but on the average case.
它的运行时间也渐近n log n，但在最坏的情况下，例如，与合并排序算法不同，但在平均情况下。
This is because this algorithm is randomized, so it uses random numbers to sort the given n objects.
这是因为该算法是随机的，因此它使用随机数对给定的n个对象进行排序。
Well, we will explain later in this lesson what this means.
那么，我们将在本课后面解释这意味着什么。
Finally, as I said before, this algorithm is very efficient in practice and, at the same time, not so difficult to implement.
最后，正如我之前所说，这种算法在实践中非常有效，同时也不是那么难以实现。
This is a toy example explaining the main idea of the quick sort algorithm.
这是一个玩具示例，解释了快速排序算法的主要思想。
So given an array, in this case of size 11, let's take its first element.
所以给定一个数组，在这个大小为11的情况下，让我们看看它的第一个元素。
In this case it is 6.
在这种情况下它是6。
And let's do the following.
让我们做以下几点。
Let's rearrange all the elements in this array such that the element 6 stays in its final position.
让我们重新排列该数组中的所有元素，使元素6保持在其最终位置。
All the elements that go before it are actually at most 6.
之前的所有元素实际上最多为6。
And all the elements that go after 6, after this element, are greater than 6.
在此元素之后，6之后的所有元素都大于6。
Well, we will show that this can be done by a single scan of the initial array.
好吧，我们将证明这可以通过初始数组的单次扫描来完成。
This is how the resulting array looks like.
这就是生成的数组的样子。
So once again, 6 stays in its final position.
所以再一次，6人保持在最终位置。
All the elements before it are at most 6.
之前的所有元素最多为6。
All the elements after it are greater than 6.
之后的所有元素都大于6。
So we do not need to move 6 anymore.
所以我们不再需要移动6了。
It is already in its final position.
它已经处于最终位置。
So what remains to be done is to sort all the elements that go before 6 and all the elements that go after 6.
所以还有待做的是对6之前的所有元素和6之后的所有元素进行排序。
And this can be done just with two recursive calls to the same algorithm, to the quick sort algorithm.
这可以通过对同一算法的两次递归调用到快速排序算法来完成。
So we do this, and immediately after these two recursive calls, we have a sorted array.
所以我们这样做，并且在这两个递归调用之后，我们有一个排序数组。
Well, in the next video we will explain all the details of this algorithm.
那么，在下一个视频中，我们将解释该算法的所有细节。
------------- 44 -------------
02算法
In this video, we'll provide the full outline of the Greek word algorithm.
在本视频中，我们将提供希腊词算法的完整大纲。
So as you remember that algorithm is recursive, for this reason we pass through this procedure [INAUDIBLE] a and also doing this is l and r in this array for left and right and this procedure saw the sub array inside r within this is form l to r.
所以当你记得算法是递归的时候，为此我们通过这个过程[听不清] a并且在这个数组中左右都是l和r这个过程看到r里面的子数组是形式l到r。
Well we first check whether l is at least r.
那么我们首先检查l是否至少是r。
And if yes then this means that they can respond in sub array contains at most one element.
如果是，那么这意味着他们可以在子数组中响应最多包含一个元素。
And this in turn means that nothing needs to be done so we just return.
而这反过来意味着什么都不需要做，所以我们才回来。
Otherwise we call the partition procedure with the same parameters.
否则，我们使用相同的参数调用分区过程。
It returns an index m between l and r.
它返回l和r之间的索引m。
So it rearranges all the elements inside this sub array with the following property.
因此，它使用以下属性重新排列此子数组中的所有元素。
After the call to this procedure, A of m stays in its final position, meaning that all the elements to the left of an element A of m are at most A of m.
在调用此过程之后，m的A保持在其最终位置，这意味着m的元素A左侧的所有元素最多为m的m。
And all the elements to the right are greater than A of m.
右边的所有元素都大于m的a。
Well once again, after the call to the partition procedure, A of m stays in its final position.
再一次，在调用分区程序之后，m中的A保持在其最终位置。
So what remains to be done is to sort all the elements that are at most A to m.
因此，还有待完成的是对最多A到m的所有元素进行排序。
They stay to the left of A of m, and all the elements that stay to the right.
他们留在A的左边，以及留在右边的所有元素。
So we do this just by making two recursive calls.
所以我们只需要进行两次递归调用即可。
So this is how the wall algorithm looks pictorially.
所以这就是墙算法的图像。
Again, we are given an array A, with two indices l and r, and we are going to sort the sub array inside from indices L to R.
再次，我们给出一个数组A，有两个索引l和r，我们将从索引L到R内部对子数组进行排序。
So with first call the participation procedure which parameter A, l and r.
因此首先调用参数A，l和r的参与程序。
And it gives us an index m between l and r was the following property.
并且它给出了l和r之间的索引m是以下属性。
All elements to the left of them are at most the element A of m.
它们左边的所有元素最多都是m的元素A.
All the elements to the right are great as an A of m.
右边的所有元素都很棒，作为m的一个。
Then we make two recursive calls to sort the left part within this is from l to m- 1 and to solve the right part within this is from m + 1 to r.
然后我们进行两次递归调用，对其中的左边部分进行排序，从l到m-1，并解决其中的右边部分是从m + 1到r。
And immediately after these two recursive call, we have a sorted array.
在这两个递归调用之后，我们有一个排序数组。
So before showing the actual of the partition procedure, we explain it's main ideas again, on a toy example.
因此，在展示分区程序的实际情况之前，我们再次在一个玩具示例中解释它的主要想法。
So first of all, we will take is the element A[l] and denoted by x.
首先，我们将采用元素A [l]并用x表示。
This will be called our pivot element.
这将被称为我们的枢轴元素。
So what pivot is exactly is the element with respect to which we're going to partition our sub array.
那么什么是枢轴才是我们要对子数组进行分区的元素。
So x will be placed in its final position.
因此x将被置于其最终位置。
So our goal now is to rearrange all the elements inside our current sub array so that x stays in its final position and all the elements to the left of x.
所以我们现在的目标是重新排列当前子数组中的所有元素，使x保持在其最终位置，并且x的左侧包含所有元素。
At most x and all the elements to the right of x are greater than x.
最多x和x右边的所有元素都大于x。
So we will do this gradually increasing the region of already discovered elements.
因此，我们将逐步增加已发现元素的区域。
So for this we will use a counter i, and we will maintain the following invariant.
因此，我们将使用计数器i，我们将保持以下不变量。
So I will go from l + 1 to r, and at each point of time when we have already have the i element we will keep to region in sizes these region from l + 1 to i.
所以我将从l + 1转到r，并且在我们已经拥有i元素的每个时间点，我们将保持区域的大小，这些区域从l + 1到i。
In the first region from l + y to j, we will keep all elements that are at most x.
在从l + y到j的第一个区域中，我们将保留最多x的所有元素。
In the second adjacent region within this is from j + 1 to i we will have all elements that are greater than x.
在第二个相邻区域内，从j + 1到i，我们将拥有大于x的所有元素。
Let's see it for example.
让我们看看它的例子。
So I assume that we are somewhere in the middle of this process.
所以我假设我们处于这个过程的中间位置。
In this case, x is equal to 6, and we need to partition all the elements with respect to x.
在这种情况下，x等于6，我们需要相对于x对所有元素进行分区。
We already have two sub regions so in the red region, we keep all elements that are at most x.
我们已经有两个子区域，所以在红色区域，我们保留最多x的所有元素。
There are at most 6 in the blue region we have holds elements that are greater than 6.
蓝色区域中最多有6个我们拥有大于6的元素。
Okay, now we move i to the next position and we discover the element 9.
好的，现在我们将i移动到下一个位置，然后我们发现了元素9。
So this element is greater than 6, so we just need to extend the second region, the blue region.
所以这个元素大于6，所以我们只需要扩展第二个区域，即蓝色区域。
The region of elements is at greater than 6.
元素区域大于6。
So in this case we just do nothing.
所以在这种情况下我们什么都不做。
Well the next case is more interesting, we move i to the next position, and we discover the element 4.
那么下一个案例会更有趣，我们将我移动到下一个位置，然后我们发现元素4。
In this case, we need to somehow move this element to the red region, to the region of elements which at most 6.
在这种情况下，我们需要以某种方式将此元素移动到红色区域，移动到最多6个元素的区域。
So to do this we just swoop it to currently first element of the blue region, in this case was 9.
所以为了做到这一点，我们只是把它猛扑到蓝色区域的当前第一个元素，在这种情况下是9。
So if we do this 4 will be the last element of currently red region and 9 will go to the blue region.
因此，如果我们这样做，4将是当前红色区域的最后一个元素，9将转到蓝色区域。
So we do this and now, we increase also the just to reflect the fact that our red region had just been extended.
所以我们这样做，现在，我们也增加了正义，以反映我们的红色区域刚刚扩展的事实。
Then we will find to the next element so we discover element 7 which is greater than 6 which means that we can just extend the blue region, then we discover another element which is 6.
然后我们将找到下一个元素，因此我们发现元素7大于6，这意味着我们可以只扩展蓝色区域，然后我们发现另一个元素是6。
6 is at most 6 and it is actually equal to 6, so we need to move it to the red region.
6最多为6，实际上等于6，所以我们需要将它移动到红色区域。
Again, we swap it with the first element of the blue region and then we extend the red region.
再次，我们将它与蓝色区域的第一个元素交换，然后我们扩展红色区域。
We increase g to reflect the fact that the red region has just been extended, then we discover another element, which is at most 6.
我们增加g以反映红色区域刚刚扩展的事实，然后我们发现另一个元素，最多为6。
We move it to the end of the red region.
我们将它移动到红色区域的末尾。
And finally, what we also need to do in the very end is to move the pivot element which is 6 in this case to its final position.
最后，我们最后还需要做的是将在这种情况下为6的枢轴元件移动到其最终位置。
And its final position actually can easily be found in this case.
在这种情况下，它的最终位置实际上很容易找到。
So we have red region and we have blue region.
所以我们有红色区域，我们有蓝色区域。
In red region, all the elements are at most 6, and in blue region, all the elements are greater than 6.
在红色区域中，所有元素最多为6，而在蓝色区域中，所有元素都大于6。
So we can just swap 6 with the last element of the red region.
所以我们可以用红色区域的最后一个元素交换6。
In this case it is 1, so if we swap these two elements then you can see that all the elements in the blue region are indeed greater than 6.
在这种情况下它是1，所以如果我们交换这两个元素，那么你可以看到蓝色区域中的所有元素确实大于6。
All the elements in the red region are smaller than 6.
红色区域中的所有元素都小于6。
So we are done with this partition procedure.
所以我们完成了这个分区过程。
Where now ready to present the Soutacot of the petition procedure.
现在准备提出请愿程序的Soutacot。
We called it what we're going to do is to place some element x, which is called the pivot, into it's final place so that all the elements before x are at most x and all the elements after x is greater than x.
我们称之为我们要做的是将一些元素x（称为枢轴）放入其最终位置，以便x之前的所有元素最多为x，x之后的所有元素都大于x。
So as the pivot element in this procedure, we are going to use just the first element of the correspondence of rate, so x is assigned A of l.
因此，作为此过程中的pivot元素，我们将仅使用rate的对应关系的第一个元素，因此x被指定为l的l。
We're also going to remain the following subregions.
我们还将继续留在下列次区域。
So first of all, we will readily increase the region of discovered elements.
首先，我们将很容易地增加已发现元素的区域。
So i goes from l +1 to r and inside this region of [INAUDIBLE] elements, we will maintain two sub regions.
所以我从l + 1到r并且在[INAUDIBLE]元素的这个区域内，我们将保持两个子区域。
In the first region with indices from l +1 to j, we will keep all of the elements at most x.
在索引从l + 1到j的第一个区域中，我们将所有元素保持在最多x。
In the second region with indices from j+1 to i, we will keep all of the elements that are greater than x and we will gradually and freeze the value of i.
在从j + 1到i的索引的第二个区域中，我们将保留所有大于x的元素，并且我们将逐渐并冻结i的值。
So when i is increased, so I assumed that i has just been increase so we discovered a new element of A of i.
所以当我增加时，我假设我刚刚增加，所以我们发现了一个新的元素。
So if A of i is greater than x then just the second of region of elements that are greater than x, is extended automatically and we do not need to do anything in this case.
因此，如果i的a大于x，那么只有大于x的元素区域的第二个区域会自动扩展，在这种情况下我们不需要做任何事情。
However, if the newly discovered element is at most x, then we need to move it to the first region.
但是，如果新发现的元素最多为x，那么我们需要将其移动到第一个区域。
So we do this as follows.
所以我们这样做如下。
So we just increase the value of j to indicate the fact that the first region has just been increased, and then swap the elements.
所以我们只是增加j的值来表示第一个区域刚刚增加的事实，然后交换元素。
A[j] and A[i], so this way, we just maintain our invariant each time when i is increased.
A [j]和A [i]，所以这样，每当我增加时，我们只保持不变量。
So in the very end, when i reaches the value of r, we also need to place our initial element that states that at the beginning our pivot between our two regions.
所以在最后，当我达到r的值时，我们还需要放置我们的初始元素，该元素在开始时指出我们两个区域之间的枢轴。
So for this we just swap elements A[l], so this is our pivot with element A[j].
所以为此我们只交换元素A [l]，所以这是我们的元素A [j]的支点。
And we then return the value j as an index of our pivot element.
然后我们返回值j作为pivot元素的索引。
------------- 45 -------------
03随机枢轴
Now when the algorithm is present, we need to estimate the running time.
现在，当算法存在时，我们需要估计运行时间。
For the Quicksort algorithm, the running time analysis is a little bit tricky.
对于Quicksort算法，运行时分析有点棘手。
So before stating, and proving the theorem about it's running time, let's be allowing partition.
所以在陈述并证明关于它的运行时间的定理之前，让我们允许分区。
First of all, let's consider a pathological case, when somehow, it always happens that we select the minimum value of our current subarray as our pivot element.
首先，让我们考虑一个病态案例，当某种程度上，我们总是选择当前子阵列的最小值作为我们的枢轴元素。
Well in this case, well let's see what happens with our current subarray.
那么在这种情况下，让我们看看我们目前的子阵列会发生什么。
Say of size n.
说大小n。
And we select its minimum value as a pivot.
我们选择其最小值作为支点。
And partition, the subarray with respect to the sum.
和分区，关于总和的子阵列。
Since this is the minimum value, it's final position is just the first position, is the resulting array, right? Which means that we partition into two parts.
由于这是最小值，它的最终位置只是第一个位置，是生成的数组，对吗？这意味着我们分为两部分。
The first part is just empty, we have no elements smaller than our pivot.
第一部分是空的，我们没有比我们的支点小的元素。
And the second part, contains n- 1 elements, because all the remaining elements are greater than our current element.
第二部分包含n-1个元素，因为所有剩余元素都大于我们当前元素。
Okay, so in this case, if this happens at this iteration, I mean at this call to partition procedure, then we can write the running time of our Quicksort algorithm, satisfies the following relation T of n is equal to n plus t of n minus one.
好吧，所以在这种情况下，如果在这次迭代中发生这种情况，我的意思是在调用分区程序时，我们就可以编写Quicksort算法的运行时间，满足以下关系：n的n等于n加n的t减一。
The term n here, the response to the running time of the petition procedure.
这里的术语n是对请愿程序的运行时间的响应。
Well, it is actually big often.
嗯，它实际上经常很大。
But just to simplify let's put n here.
但只是为了简化让我们把n放在这里。
Let me also recall you that, well if we have an array of size n, then the partition procedure indeed works in time, big often, because it just becomes the subarray? So now let's see what is the solution for this recurrence relation.
让我也记得你，如果我们有一个大小为n的数组，那么分区程序确实可以及时运行，通常很大，因为它只是变成了子阵列？那么现在让我们看看这种递归关系的解决方案是什么。
Well, we can just unwind this recurrence relation term by term.
那么，我们可以按期限解除这个递归关系项。
So we have n plus T of n minus 1.
所以我们有n加T的n减1。
Let's replace T of n minus 1 by n minus 1 plus T of n minus 2.
让我们将n减1替换为n减1加上n减去2的T。
Then we replace T of n minus 2 by n minus 2 plus T of n minus 3.
然后我们将n减2的T替换为n减2加上n减3的T.
And we keep doing so.
我们一直这样做。
So what is left is the following sum, n + (n- 1) + (n- 2) and so on.
所以剩下的是以下和，n +（n-1）+（n-2）等等。
So what we know is this sum already, so this is arithmetic series.
所以我们所知道的就是这个数字，所以这是算术系列。
And we know that it grows quadratically.
我们知道它会以二次方式增长。
Which give us something strange, I mean our Quicksort algorithm works in quadratic time.
这给了我们一些奇怪的东西，我的意思是我们的Quicksort算法在二次时间内工作。
Which means that it is not quick, actually, right? We'll resolve this issue later.
这意味着它不快，实际上，对吧？我们稍后会解决这个问题。
Now, let's consider a slightly different case.
现在，让我们考虑一个稍微不同的情况。
Assume that somehow, we always partition into two parts, such that one of them has size, for example, n- 5.
假设不知何故，我们总是分成两部分，例如，其中一部分具有大小，例如，n-5。
And the other one has the size four.
而另一个的大小为四。
Well I claim that even in this case.
我声称即使在这种情况下也是如此。
First of all, note that both these cases correspond to very unbalanced partitions.
首先，请注意这两种情况都对应于非常不平衡的分区。
In the first case, we have two parts one of size 0 and one of size n-1.
在第一种情况下，我们有两个部分，一个是0号，另一个是n-1。
In the second case, we have two parts one of size five.
在第二种情况下，我们有两个部分，一个是五个。
And one of size four and one of size n minus five.
其中一个是四号和一号，大小为n减五。
So the size of stuff parts are very unbalanced.
所以零件的尺寸非常不平衡。
They are very different.
他们是非常不同的。
Okay, so I claimed that in this case the running time, is also going to be quadratic.
好的，所以我声称在这种情况下，运行时间也是二次方的。
And this can also be shown, just be unwinding this recurrence relation.
这也可以显示，只是解除这种递归关系。
So let's just throw away this T(4), and leave only T(n- 5).
所以，让我们扔掉这个T（4），只留下T（n-5）。
Okay, so T(n) is equal to n plus T(n-5).
好的，所以T（n）等于n加T（n-5）。
Let's replace T(n-5) with (n-5)+T(n)-10.
让我们用（n-5）+ T（n）-10代替T（n-5）。
Let's then replace T of n minus ten with T of n with n minus ten plus T of n minus 15 and so on.
然后让n替换为T减去十，其中t为n，其中n减去10加上T减去15，依此类推。
So this leaves us with the following sum.
所以这给我们留下了以下总和。
N plus n minus five plus n minus ten and so on and this is also an arithmetic progression.
N加n减5加n减10等等，这也是算术级数。
The only difference with the previous arithmetic progression is that now, we have step five.
与先前算术级数的唯一区别在于，现在，我们有第五步。
The difference between neighbors is five, but not one.
邻居之间的差异是五，但不是一个。
Well, still, this arithmetic progression has a linear number of terms.
嗯，这个算术级数仍然是线性的项数。
Which means that it sums rows quadratically.
这意味着它以二次方式对行进行求和。
With the only difference that the hidden constant inside this set up is smaller than in the previous case.
唯一的区别是此设置中的隐藏常量小于前一种情况。
Now let's consider another pathological case.
现在让我们考虑另一个病态案例。
Assume that it somehow so happens for some unknown reasons that at each iteration at each call there's a partition procedure.
假设它出于某些未知原因以某种方式发生，在每次调用的每次迭代中都有一个分区过程。
It partitions the array into roughly equal sizes.
它将数组分成大致相等的大小。
Well in this case we can write the following reference relation on the running time of our algorithm.
那么在这种情况下，我们可以在算法的运行时间上写下以下参考关系。
T of n is equal to T of n over 2 plus the linear term.
n的t等于2的T加上线性项。
And we know this reference already.
我们已经知道了这个参考。
It is exactly the reference the running time of the satisfies.
它正是参考运行时间的满足。
Right? And we, proved that in this case t of n grows as n increases vertically.
对？我们证明了在这种情况下，随着n垂直增加，n的t增长。
Let me remind you, how we prove this.
让我提醒你，我们如何证明这一点。
We analyzed the.
我们分析了。
So, in this three of the route we have one array of size n.
所以，在这三个路线中，我们有一个大小为n的数组。
At the next level we have two arrays of size n over two n, at the next level we have four rays of size n over four, and so on.
在下一个级别，我们有两个大小为n超过两个n的数组，在下一个级别，我们有四个大小为n的四条光线，依此类推。
So the height of this tree is log base two, well it is basically logarithmic.
所以这棵树的高度是log base 2，它基本上是对数的。
At each level the sum of the sizes of of full arrays is equal to N.
在每个级别，完整数组的大小总和等于N.
So we have array of size N at the top, two arrays of size N over two at the next level, and four arrays of size N over four at the next level, the size is still N, and so on.
因此，我们在顶部有大小为N的数组，在下一级有两个大小为N的数组，在下一级有四个大小为N的数组，大小为N，依此类推。
At each level we spend a linear amount of work.
在每个级别，我们花费大量的工作。
This is essential.
这很重要。
We spend a linear amount of work at each level, and we have a logarithmic number of levels, which means we spent an N log N in time total.
我们在每个级别上花费了线性的工作量，并且我们有一个对数的级别，这意味着我们在总时间上花费了N log N.
Okay, let's consider another, again very pathological case.
好吧，让我们考虑另一个非常病态的案例。
I assume that we alway split an array of size n into two parts.
我假设我们总是把一个大小为n的数组分成两部分。
One of size n over 2, n over 10.
尺寸n超过2，n超过10。
I'm sorry.
对不起。
One of size 9n over 10.
尺寸9n超过10。
So in this case the recurrence is the following.
所以在这种情况下，重复发生如下。
T of n is equal to T of n, over 10.
n的T等于n的T，超过10。
Plus T of 9N over 10 plus a linear term.
加上9N超过10的T加上一个线性项。
I claim that even in this case we can prove [INAUDIBLE] again on the running time of how well and this is how we can do this.
我声称即使在这种情况下，我们也可以在运行时间上再次证明[听不清]，这就是我们如何做到这一点。
Well, lets again consider the [INAUDIBLE] because the [INAUDIBLE] of [INAUDIBLE] algorithm.
好吧，让我们再考虑[听不清]，因为[听不清]算法的[听不清]。
In this case, it is not balanced.
在这种情况下，它是不平衡的。
Right? Because when we go to the left branch, we reduce the size of the current subproblem by 10.
对？因为当我们转到左分支时，我们将当前子问题的大小减小10。
And when we go to the right branch, we reduce the size of the current subproblem only by factor of 10 divided by 9.
当我们进入正确的分支时，我们只将当前子问题的大小减少10倍除以9。
Which means that in our 3, the size of the left branch is of the left most branch, is actually log based ten.
这意味着在我们的3中，左分支的大小是最左边的分支，实际上是基于日志的十分。
Of n while is the size of the right most branch is log based ten over nine over m.
在n的同时，最右边的分支的大小是以m为基数的十分之九。
Well, still the height of this of this three is logarithmic.
那么，这三者的高度仍然是对数。
But the previous case is that nouns are based on the algorithm is different but it's still constant.
但前一种情况是名词基于算法不同但它仍然是不变的。
It is log based, log based 9 of m.
它是基于日志的，基于日志的m为m。
And also, but also, the previous property is true.
而且，之前的属性也是如此。
The sum of the sizes of all arrays at each level is still equal to n.
每个级别的所有数组的大小总和仍然等于n。
It is at most n, actually.
实际上它至多是n。
At the root we have one array of size n.
在根目录，我们有一个大小为n的数组。
At the next level we have two arrays, one of size n/10, and the other one is of size 9n/10.
在下一级，我们有两个数组，一个是大小为n / 10，另一个是9n / 10。
Right? So the size is still n.
对？所以尺寸仍然是n。
At the next level it is the same, and so on.
在下一个级别它是相同的，依此类推。
So we have a logarithmic number of levels, and at each level we spend a linear amount of work which gives us an n log n upper bound once again.
所以我们有一个对数的级别，在每个级别我们花费一定数量的工作量，这使我们再次获得n log n上限。
Okay, all this analysis of what about only pathological cases if we always split in a balanced way or in an unbalanced way.
好吧，如果我们总是以平衡的方式或以不平衡的方式分裂，那么所有这些只分析病理案例的分析。
In reality, or just when we run a Greek algorithm on some array, well some of the partitions are going to be balanced.
实际上，或者只是当我们在某个阵列上运行希腊算法时，一些分区将会平衡。
Some of the partitions are going to be unbalanced.
一些分区将是不平衡的。
So will still do not know what is the actual running time of the Greek algorithm.
所以仍然不知道希腊算法的实际运行时间是多少。
We still need to determine this.
我们仍然需要确定这一点。
However, we already get an important message.
但是，我们已经收到了重要信息。
So running time of Algorithm of the Greeks are depends on how balanced our partitions.
因此，希腊人算法的运行时间取决于我们的分区如何平衡。
What we know know is the following, if all our politicians are balanced does that make improved that the running time is at most n log n hypothetically.
我们所知道的是以下内容，如果我们所有的政治家都是平衡的，那么可以改善运行时间至少是假设的。
At the same time if all of our partitions are unbalanced then the running time is quadratic.
同时，如果我们所有的分区都不平衡，那么运行时间是二次的。
This means that we would like to have a way of selecting a pivot element such that it always guarantees a balanced partition.
这意味着我们希望有一种选择枢轴元素的方法，以便始终保证平衡分区。
At the same time it is not clear at all how to do this.
同时，根本不清楚如何做到这一点。
How to guarantee that we can always peek quickly.
如何保证我们总能快速窥视。
The pivot element with respect to this pivot, the rate is partitioned in a balanced way.
枢轴元件相对于该枢轴，速率以平衡的方式分开。
So instead of this we will use the following elegant solutions, so let's just select the pivot element from the current subarray randomly.
因此，我们将使用以下优雅的解决方案来代替这一点，所以让我们随机选择当前子阵列中的pivot元素。
To implement this solution, we do the following.
要实现此解决方案，我们执行以下操作。
Before following the partition procedure.
在执行分区过程之前。
We just select a random index between l and m, and we swap elements A[l] and this random element.
我们只选择l和m之间的随机索引，然后我们交换元素A [l]和这个随机元素。
Okay, then we call partition, and then we proceed in a usual way.
好的，然后我们调用分区，然后我们以通常的方式进行。
Let me explain intuitively why selecting a random partition is going to help us to prove a good upper bound on the running time of the Quicksort algorithm.
让我直观地解释为什么选择随机分区将帮助我们证明Quicksort算法运行时间的良好上限。
Well, for this, consider array A's that we're going to partition with respect to random p and consider it sorted version.
好吧，为此，考虑我们将要对随机p进行分区的数组A并考虑它的排序版本。
Assume for the moment that all the elements inside our array are different.
假设我们阵列中的所有元素都是不同的。
In the sorted version, consider the middle half elements.
在排序版本中，考虑中间的半个元素。
Well we can see that n/2 elements that stay exactly in the middle.
好吧，我们可以看到n / 2元素完全保持在中间。
Well an important property of all these elements is the following: for each of these n/2 elements there are at least n/4 elements that are greater than them.
所有这些元素的重要特性如下：对于这些n / 2元素中的每一个，至少有n / 4个元素大于它们。
And at least n over four elements that are smaller.
并且至少n超过四个较小的元素。
Well this means that if we select any of these elements inside our array a, then the partition with respect to this element is going to be balanced.
嗯，这意味着如果我们在数组a中选择这些元素中的任何一个，那么关于这个元素的分区将是平衡的。
Right? In both parts there will be at least n over four elements.
对？在这两个部分中，至少有四个以上的元素。
Well these n over two elements stay somewhere in the initial array.
那么这两个元素的n就会保留在初始数组中的某个位置。
So they stay in the middle in the sorted array and they stay somewhere in the initial array.
所以它们保持在排序数组的中间，它们保留在初始数组中的某个位置。
It doesn't matter for us.
对我们来说没关系。
What is important for us is that there are at least n over two elements with respect to which the partition is going to be balanced.
对我们来说重要的是，至少有两个以上的元素，分区将被平衡。
Which means that with probability one half we will have a balanced partition.
这意味着概率为一半，我们将有一个平衡的分区。
And this happens to be enough to prove it with upper bound.
这恰好足以证明它具有上限。
So we're going to show that the randomized Quicksort algorithm is actually very fast.
因此，我们将展示兰德省略Quicksort算法实际上非常快。
Well first of all it is fast in practice and we will prove it's theoretical analog out upper bound when it's running time.
首先，它在实践中是快速的，并且当它的运行时间我们将证明它是理论模拟的上限。
This is a formal statement of an upper bound on the running time of the Quicksort algorithm that we are going to prove in the next video.
这是关于Quicksort算法运行时间上限的正式声明，我们将在下一个视频中证明这一点。
So I assume that we are given an array A, and assume for the moment that all the elements of this array are pairwise different.
所以我假设给出了一个数组A，并假设此数组的所有元素都是成对不同的。
Then the average running time of the Quicksort algorithm on this array consisting of n elements, is big o of n log n.
然后Quicksort算法在由n个元素组成的数组上的平均运行时间是n log n的大数。
While the worst case running time of this algorithm is n squared.
虽然该算法的最坏情况运行时间是n平方。
Well let me explain the word on average here.
那么让我在这里平均解释一下这个词。
Well, this means that for any fixed array.
嗯，这意味着对于任何固定阵列。
So if we are very unlikely with the random beats, the running time potentially could be higher as an algorithm.
因此，如果我们不太可能使用随机节拍，那么运行时间可能会更高。
However, on average, and average is over all possible random beats.
但是，平均而言，平均值超过所有可能的随机节拍。
The running time of the QuickSort algorithm is n log n.
QuickSort算法的运行时间为n log n。
And this is true for any input.
任何输入都是如此。
So this theorem doesn't say well, for Quicksort algorithm.
对于Quicksort算法，这个定理并不好说。
For some arrays, the running time is large, for some arrays the running time is low.
对于某些阵列，运行时间很长，对于某些阵列，运行时间很短。
But on average, the running time is good enough.
但平均而言，运行时间足够好。
So it says that for any fixed rate, the average running time is then n log n.
所以它说对于任何固定的速率，平均运行时间就是n log n。
Okay, so we are going to prove this theorem in the next video.
好的，我们将在下一个视频中证明这个定理。
------------- 46 -------------
04运行时分析可选
In this video we are going to prove formally an upper bound on the running time of the randomized quick sort algorithm.
在这个视频中，我们将正式证明随机快速排序算法的运行时间的上限。
Namely we're going to prove that the running time on average of the randomized quick sort algorithm is n log n.
也就是说，我们将证明随机快速排序算法的平均运行时间是n log n。
That is it must be go for n log n.
那就是必须去n log n。
And that is, that, in the worst case, the running time is big O of n squared.
也就是说，在最坏的情况下，运行时间是n平方的大O.
Well, before going into the details of the proof.
那么，在进入证明的细节之前。
Let's again, intuition.
让我们再一次，直觉。
First of all, let's know that what we need to estimate is the number of comparisons.
首先，让我们知道我们需要估计的是比较次数。
Why is that? Well because a quick sort algorithm contains of first the call to the partition procedure and then to recursive calls.
这是为什么？好吧，因为快速排序算法首先包含对分区过程的调用，然后是递归调用。
Each of these two recursive calls is going to be unwinded into the call to partition procedure and another to small recursive calls.
这两个递归调用中的每一个都将被释放到分区过程的调用中，而另一个递归到小的递归调用。
So what is going on inside the quick sort algorithm is essentially many calls to the partition procedure.
因此，快速排序算法内部发生的事情本质上是对分区过程的许多调用。
While inside the partition procedure, what we do actually is to compare all the elements of the curve and separate who is the pivot element, right? So what we estimate is a total number of comparisons.
在分区过程中，我们实际上做的是比较曲线的所有元素并分离谁是枢轴元素，对吧？所以我们估计的是总比较数。
Which is not surprising because the quick sort algorithm is a comparison based algorithm.
这并不奇怪，因为快速排序算法是基于比较的算法。
Well, now let me also explain why balanced partitions are better for us.
那么，现在让我解释为什么平衡分区对我们来说更好。
I will explain this intuitively.
我将直观地解释这一点。
So consider this story example.
所以考虑这个故事的例子。
This array of size seven.
这个七号阵列。
Assume that we selected one as the pivot element.
假设我们选择了一个作为枢轴元素。
So we partitioned the rate is shown here on the left.
所以我们分区的费率如左图所示。
Now let's see what we now know.
现在让我们看看我们现在所知道的。
We can pair it all the elements in this array to the pivot element which is one in this case.
我们可以将此数组中的所有元素与枢轴元素配对，在这种情况下是一个元素。
So now we know that one, the final position of the pivot element is just the first position in the array.
所以现在我们知道了一个，pivot元素的最终位置只是数组中的第一个位置。
So we known that 1 is the minimum value.
所以我们知道1是最小值。
However, we know nothing about pairs of other elements, right? So we only learn that 1 is the minimum value.
但是，我们对其他元素一无所知，对吧？所以我们只知道1是最小值。
Now consider another possibility, consider the following balanced partition shown on the right.
现在考虑另一种可能性，考虑右侧显示的以下平衡分区。
So assume that we selected 4 as the pivot element.
因此，假设我们选择4作为枢轴元素。
I claimed that in this case, this partition is much better for us because we saved many subsequent comparisons.
我声称在这种情况下，这个分区对我们来说要好得多，因为我们保存了许多后续比较。
So look, in this case, in the subsequent trends of the partition precision, we are not going to compare elements 3, 1, 2 with element 6, 5, 7.
因此，在这种情况下，在随后的分区精度趋势中，我们不会将元素3,1,2与元素6,5,7进行比较。
Because we already know that all the elements to the left are for a.
因为我们已经知道左边的所有元素都是a。
As in all the elements to the right are formed.
正如所有元素都在右边形成。
Well the left part will stay in a separate recursive code and the right part well stay in a separate recursive code.
那么左边的部分将保留在一个单独的递归代码中，右边的部分将保留在一个单独的递归代码中。
So once again, balanced partitions save us a lot of comparisons that we do not need to make in the subsequent calls to partition procedure.
因此，平衡分区再一次为我们节省了许多比较，我们不需要在后续的分区过程调用中进行比较。
Another thing I would like to discuss with you before growing and know details of the proof is the following.
在成长之前我想与您讨论另一件事，并且知道证据的细节如下。
Our algorithm is randomized, so its running time and its number of comparisons depends on the random beats used inside the algorithm,.
我们的算法是随机的，因此它的运行时间和比较次数取决于算法中使用的随机节拍。
In particular for any two elements there is some probability that they are going to be compared.
特别是对于任何两个元素，它们有可能被比较。
And using this toy example shown on the slide, I would like to just build an intuition on how to estimate this probability on which factors this probability depends.
使用幻灯片上显示的这个玩具示例，我想建立一个关于如何估计这个概率所依赖的因素的概率的直觉。
So consider this small example.
所以考虑这个小例子。
So this is an array of say it's nine containing all the digits.
所以这是一个包含所有数字的九个数组。
And I would like to estimate the probability that elements 1 and 9 are going to be compared if we call randomized quick sort physics already.
如果我们称之为随机快速排序物理，我想估计元素1和9将被比较的概率。
So, let's see what happens.
那么，让我们看看会发生什么。
Assume that in the very first quarters of partition procedure, we select the elements 3 for example as the pivot element, so what happens? In this case, 1 will go to the left of 3 and 9 will go to the right side.
假设在分区过程的前几个季度，我们选择元素3作为例如枢轴元素，那么会发生什么？在这种情况下，1将位于3的左侧，9将位于右侧。
To the right of three, I'm sorry.
在三人的右边，我很抱歉。
So in this case 1 and 9 will be in different parts and they will never be compared in as a partician procedure just because they are already in different parts.
因此，在这种情况下，1和9将处于不同的部分，并且它们永远不会仅仅因为它们已经在不同的部分而作为特定程序进行比较。
Okay, for the ways it means, that we already know that 1 is smaller than 9, because 1 is smaller than 3, and 3 is smaller than 9, right? We do not need to compare them.
好吧，对于它的含义，我们已经知道1小于9，因为1小于3,3小于9，对吧？我们不需要比较它们。
Well then this happens if we select as our pivot element, any of the elements, 2, 3, 4, 5, 6, 7 or 9, 8, I'm sorry.
那么如果我们选择作为我们的枢轴元素，任何元素，2,3,4,5,6,7或9,8，就会发生这种情况，对不起。
If on the other hand we select 1 and 9 as our first pivot element, then 1 and 9 will become pivot.
另一方面，如果我们选择1和9作为我们的第一个枢轴元素，则1和9将成为枢轴。
Just because, well, if we select, for example, 9 as the pivot element, we can pivot with all the elements of our array, in particular with 1.
仅仅因为，如果我们选择9作为枢轴元素，我们可以使用数组的所有元素进行旋转，特别是使用1。
So there are two cases when 1 and 9 are compared.
因此有两种情况比较1和9。
And this is how exactly the case is when either 1 or 9 are selected as a first pivot.
这就是当选择1或9作为第一个枢轴时的情况。
In all other seven cases there are not compared.
在所有其他七个案例中都没有进行比较。
This means that the probability that they are compared are 2 over 9.
这意味着它们被比较的概率是2比9。
Okay, makes sense? Now let's try to estimate the probability that the elements three and four are compared.
好的，有道理吗？现在让我们尝试估计元素3和4的比较概率。
Well I claimed that in this case this probability is equal to 1.
我声称在这种情况下，这个概率等于1。
And the explanation is the following, there is no element inside RRE that can help the randomized weak sort algorithm to understand that 3 is smaller than 4 without comparing them.
并且解释如下，RRE中没有可以帮助随机弱排序算法理解3小于4而不进行比较的元素。
I mean for 1 and 9, there are seven such elements.
我的意思是1和9，有七个这样的元素。
All they are is elements.
它们都是元素。
I mean, if we partition with respect to any of the elements, we already know that 1 is smaller than 9 because they go to other parts.
我的意思是，如果我们对任何元素进行分区，我们已经知道1小于9，因为它们会转到其他部分。
Different parts with respect to this pivot.
关于该枢轴的不同部分。
For three and four there is no such element.
对于三和四，没有这样的元素。
So algorithm just must compare these two elements to be sure that 3 is smaller than 4.
因此算法必须比较这两个元素以确保3小于4。
So in this case the probability is 1.
所以在这种情况下概率为1。
Well this shows that the probability of comparing two elements depends on how close they are in the sorted array.
这表明比较两个元素的概率取决于它们在排序数组中的接近程度。
In particular if they're very far apart of each other than the probability is small and if they are close to each other than the probability is high.
特别是如果它们彼此相距甚远，则概率很小并且如果它们彼此接近而不是概率很高。
We will use this observation in the formal proof of our statement.
我们将在我们陈述的正式证明中使用这一观察。
We now start to formally prove an upper bound on the running time of the randomized quicksort algorithm.
我们现在开始正式证明随机快速排序算法的运行时间的上限。
For this, we introduce the following random variable.
为此，我们引入以下随机变量。
Let i and j be different indices from 1 to m.
设i和j是从1到m的不同指数。
We define Xi of ij to be equal to 1 if two elements, A'[i] and A'[j] are compared in the [INAUDIBLE] quick sort algorithm and to be equal to 0 otherwise.
如果在[听不清]快速排序算法中比较两个元素A'[i]和A'[j]，则将ij的Xi定义为等于1，否则等于0。
Once again, to estimate the running time of the quick sort algorithm, we would like to estimate the total number of comparisons made, so we would like to estimate, for any pair of elements, what is the probability that they are compared? As we discussed on the previous slide, the probability that two elements are compared depends on how close they are in the sorted version of our array.
再次，为了估计快速排序算法的运行时间，我们想估计所做的比较总数，因此我们想估计，对于任何一对元素，它们被比较的概率是多少？正如我们在上一张幻灯片中所讨论的那样，比较两个元素的概率取决于它们在数组的排序版本中的接近程度。
For this reason, we define c of ij dependent on the sorted array.
因此，我们定义依赖于排序数组的i的c。
We do not have this sorted array, right? We are only constructing this in the quick sort algorithm but we use it just for the analysis, okay? The next thing to note is the following.
我们没有这个排序的数组，对吧？我们只是在快速排序算法中构建它，但我们只是用于分析，好吗？接下来要注意的是以下内容。
For any two elements of our initial array assorted array doesn't matter, so for any two elements they are either compared just once or they are not compared at all.
对于我们的初始数组的任何两个元素，各种数组并不重要，因此对于任何两个元素，它们要么只进行一次比较，要么根本不进行比较。
So, why is that? Why just once? Well, if two elements are compared at some point, this means that at this point one of these elements is because in the partition procedure we can put a with all of the elements of the current summary.
那么，为什么呢？为什么只有一次？好吧，如果在某一点比较两个元素，这意味着此时其中一个元素是因为在分区过程中我们可以使用当前摘要的所有元素。
So, if two elements are compared that one of them is a pivot.
因此，如果比较两个元素，其中一个元素是一个支点。
This also means that right after the call of this partition procedure, we are not going to use this pivot element.
这也意味着在调用此分区过程之后，我们不会使用此pivot元素。
We will put the pivot element into its final place, and we are not going to touch it in any of the subsequent calls.
我们将把枢轴元素放到最后的位置，我们不会在任何后续调用中触摸它。
This immediately implies the quadratic upper bound on the worst case right in time with final algorithm.
这立即意味着最终情况下的最终情况的二次上界与最终算法的正确性。
Once again we have quadratic number of possible pairs of element, and each pair of element is as it compared once or not compared at all.
我们再次具有二次数量的可能元素对，并且每对元素在比较一次或根本不进行比较时。
Right so right in time with the worst case is quadratic.
在最坏的情况下及时正确是二次的。
Now comes the most important observation of this proof.
现在来看这个证明是最重要的观察。
I claim that the elements A'[i] and A'[j] are compared if and only if the first pivot selected in the subrange of the solitary a prime from either side to index j is either a prime of a, of i, or a prime of j.
我声称元素A'[i]和A'[j]被比较，当且仅当在从一侧到索引j的孤立的子范围中选择的第一个枢轴是i的一个素数时，i，或j的一个黄金。
Well let's see why.
好吧，让我们看看为什么。
First of all, when we select it pivot the random pivot which is not in their sub range, and then all the elements from this sub range in this sort of element goes either to the left or this to the right.
首先，当我们选择它时，转动不在其子范围内的随机数据轴，然后此类元素中此子范围内的所有元素将向左或向右移动。
So, they all stay together in the same branch of three, okay.
所以，他们都在三个人的同一个分支，好吧。
So before we select a pivot which stays inside this range, all these elements stay together in the same sub-array.
因此，在我们选择一个保持在此范围内的枢轴之前，所有这些元素都保持在同一个子阵列中。
Now, assume that we selected a pivot from this sub-range, and assume that it is not A'[i] or A'[j], for example.
现在，假设我们从该子范围中选择了一个枢轴，并假设它不是A'[i]或A'[j]，例如。
In this case a prime of A and a prime of J will be splitted apart.
在这种情况下，A的素数和J的素数将被分开。
They will go into different parts with respect to this pivot, right? At this point I must humor that all the elements in my summary are different, and in duality are different, okay? So once again, if the first selected element from this subrange is not prime of A or a prime of j then these two elements are not going to be compared.
关于这个支点，他们将分为不同的部分，对吧？在这一点上，我必须幽默，我的总结中的所有元素都是不同的，并且二元性是不同的，好吗？因此，如果此子范围中的第一个选定元素不是A的素数或j的素数，那么这两个元素将不会被比较。
Because right after the partition procedure uses this pivot from this range A prime of a and A prime of j will go to different parts, right? If, on the other hand, the first selected pivot from this subrange is either A prime of a or A prime of j, then these two elements are going to become paired, right? So this is the most important observation in this proof.
因为在分区程序之后立即使用此范围中的此枢轴，a的a和a的素数将转到不同的部分，对吧？另一方面，如果来自该子范围的第一个选定的枢轴是a的素数或者是j的素数，那么这两个元素将成为配对，对吧？所以这是这个证明中最重要的观察。
Everything else is just calculations.
其他一切都只是计算。
So if this is clear, let's then estimate the probability that second respondent to elements are compared.
因此，如果这一点很清楚，那么让我们估计第二个对元素的响应者进行比较的概率。
So we know that they're compared if and only if the first selected Pivot in this sub range is one of these two elements.
因此我们知道，当且仅当此子范围中的第一个选定的Pivot是这两个元素中的一个时，才对它们进行比较。
This helps us to estimate the probability of not the fact that c of i j is equal to one.
这有助于我们估计不是i的c等于1的概率。
Well this is equal to two.
那么这相当于两个。
I mean because we have only two choices.
我的意思是因为我们只有两个选择。
I mean either a prime of a, or a prime of j divided by the total number of choices, I mean the total number of elements in this subrange.
我的意思是要么是a的素数，要么是j的素数除以选择的总数，我的意思是这个子范围中的元素总数。
And this is j minus i plus 1.
这是j减去i加1。
So the probability that Z of ij is equal to 1 equals 2 divided by g minus i plus 1.
因此，ij的Z等于1的概率等于2除以g减去i加1。
For example, if j and i differ by 1.
例如，如果j和i相差1。
So j is equal to y plus 1.
所以j等于y加1。
So neighboring element in the.
所以邻近的元素。
Then this probability is equal to 2 divided by 1 plus 1.
那么这个概率等于2除以1加1。
This is 2 by 2, this is 1.
这是2乘2，这是1。
[INAUDIBLE] Just reflects the fact that if there are two neighboring elements inside.
[听不清]只是反映了如果内部有两个相邻元素的事实。
This sorted array, then the algorithm just must compare them, to understand that one of them is smaller.
这个排序的数组，然后算法只需要比较它们，以了解其中一个更小。
There is no other element that can help our algorithm to realize that one of these element is smaller than the other one, okay.
没有其他元素可以帮助我们的算法实现这些元素中的一个比另一个小，好吧。
This in turn helps us to estimate the expected value of this random variable.
这反过来有助于我们估计这个随机变量的期望值。
So recall that if we have a random variable, which takes only values zero and one, then its expected value is one multiplied by the probability that it takes value one plus zero multiplied by the probability that it takes the value zero.
所以回想一下，如果我们有一个随机变量，它只取值0和1，那么它的期望值就是乘以一个加零的概率乘以它取值为零的概率。
Well zero multiplied by something is zero.
零点乘以某物为零。
So what is left is just probability.
所以剩下的只是概率。
That it takes multiplied by one.
它需要乘以一。
So the expected value of CIJ is equal to 2 divided by g minus i plus one.
所以CIJ的预期值等于2除以g减去i加1。
The final step in our proof is estimating the sum random variables to see they all possible I and J.
我们证明的最后一步是估计总和随机变量，看看它们都是可能的I和J.
So, once again the expected value of average value of the sum of the number of comparisons made is the expected value of the sum of all possible x adjacent, or for all I Js.
因此，所进行的比较次数之和的平均值的预期值再次是所有可能的x邻近或所有I Js的总和的期望值。
So the expected value of their sum is the sum of their expected values.
因此，它们的总和的期望值是它们的预期值的总和。
So we can write the following.
所以我们可以写下面的内容。
The average running time is equal to the sum overall possible different of the expected values cij, and we know this expected value already.
平均运行时间等于预期值cij的总体可能总和，我们已经知道这个预期值。
So this is a some overall possible different ij, in where j is greater than i of 2 divided by g minus i plus one.
所以这是一个总体可能不同的ij，其中j大于i的2除以g减去i加1。
Well we can take this constant two out, and consider all the possible.
好吧，我们可以把这两个常数拿出来，并考虑所有可能的。
And consider a fixed i.
并考虑一个固定的i。
For this i what we have j ranges from i+1 to n.
为此，我们所拥有的j的范围从i + 1到n。
So what we have for the specified time in this sum is a subset of the following sum, 1/2+1/3+1/4 and so on.
因此，我们在此总和中指定时间的内容是以下总和的子集，1/2 + 1/3 + 1/4，依此类推。
And this is actually a known sum.
这实际上是一个已知的总和。
This is called harmonic series and it is known that it grows arithmetically.
这被称为谐波系列，并且已知它在算术上增长。
Once again, 1 over 2 plus 1 over 3 plus, and so on, 1 over n, is theta of logarithm of n.
再一次，1比2加1加3加，依此类推，1比n，是n的对数θ。
Well, this means that, for each they correspond in sum, which ranges over all j from i plus 1 through n, grows, at most, logarithmically.
嗯，这意味着，对于每个它们总和相对应的范围，从i加1到n的所有j的范围，最多以对数方式增长。
This means since we have m traces for i from one to m that the grows vertically as m.
这意味着因为我们有一条从i到m的m轨迹，所以m垂直增长为m。
Okay, and this concludes our proof.
好的，这就是我们的证据。
------------- 47 -------------
05相等的元素
In this video we address the issue of equal elements in the.
在这个视频中，我们解决了相同元素的问题。
So recall that we proved the upper bound on the running time of the render Greek algorithm, in the assumption that all the elements inside the given array are prioritized different.
所以回想一下，我们证明了渲染希腊算法的运行时间的上限，假设给定数组中的所有元素的优先级不同。
And actually, we used essentially these assumptions.
实际上，我们基本上使用了这些假设。
So, recall that we estimated the probability that two elements, A prime of I and A prime of J are comparative.
因此，回想一下，我们估计了两个元素的概率，即I的素数和J的素数是比较的。
And we argued that if any element between them is selected, the appearance is that they will not become period.
我们认为如果选择它们之间的任何元素，那么外观就是它们不会成为句号。
However, if they are equal, so if A prime of A is equal to A prime of J, this means actually that all the elements in this range are equal.
但是，如果它们相等，那么如果A的素数等于J的素数，这实际上意味着该范围内的所有元素都是相等的。
So if we select any element inside this range, in the middle of this range, as a pivot, then it is not true that these two elements will go into different parts with respect to this element, this is just because all of the elements inside this range are equal, which means that if we partition with respect of this element, all of the elements in this range will be [INAUDIBLE] this element.
因此，如果我们选择此范围内的任何元素，在此范围的中间，作为一个枢轴，那么这两个元素相对于此元素将进入不同的部分并不是真的，这只是因为内部的所有元素这个范围是相等的，这意味着如果我们对这个元素进行分区，这个范围内的所有元素都将是[INAUDIBLE]这个元素。
So, they all will be in the left part with respect to this element, okay? So our analysis doesn't work for equal elements but let's see what happens in real life.
所以，他们都将在这个元素的左边部分，好吗？因此，我们的分析不适用于相同的元素，但让我们看看现实生活中会发生什么。
What happens if we run the greek sort algorithm for the array in which there are equal elements.
如果我们为具有相同元素的数组运行希腊排序算法会发生什么。
For this, let's use the following online visualization.
为此，我们使用以下在线可视化。
This visualization shows how different selection, different certain algorithms that are formed on different datasets.
此可视化显示了不同的选择，不同的特定算法在不同数据集上的形成方式。
So there are eight certain algorithms here where we are now interested in this QuickSort algorithm.
因此，这里有八种特定算法，我们现在对这种QuickSort算法感兴趣。
And there are four different types of datasets.
并且有四种不同类型的数据集。
So the field datasets is just random sequence.
因此，字段数据集只是随机序列。
The next one is in sorted sequence, the next one is a reversed sequence and the next one which is most interesting to us at the moment is a sequence that contains a few unique elements.
下一个是排序顺序，下一个是反向序列，下一个对我们来说最感兴趣的是包含一些独特元素的序列。
So let's see how the greek sort algorithm performs on the last dataset.
那么让我们看看希腊排序算法如何在最后一个数据集上执行。
So for this let's just run all the algorithms, on all data sets.
所以为此，我们只需在所有数据集上运行所有算法。
So let's see what happens here.
那么让我们看看这里发生了什么。
So you, you may notice now that, for example, have already sorted everything.
那么你，你可能会注意到，例如，已经对所有东西进行了排序。
And while greek sort have just finished to sort the last, the last data set.
虽然希腊排序刚刚完成排序最后一个，最后一个数据集。
So Greek sort is not, is not so fast on data sets that contains few unique elements and this is why.
所以希腊排序不是，在包含很少独特元素的数据集上不是那么快，这就是原因。
So just consider a dataset that consists of elements that are all equal to each other.
因此，只需考虑一个由彼此相等的元素组成的数据集。
So all elements are equal to each.
所以所有元素都等于每个元素。
This means that the selection, the partition procedure always partitions the array with respect to the element x, right? And then in this case, one of the parts, namely the part of the elements that are greater than x, is just empty.
这意味着选择，分区过程总是相对于元素x对数组进行分区，对吗？然后在这种情况下，其中一个部分，即大于x的元素部分，只是空的。
It has size zero.
它的大小为零。
And the other part has size n minus one.
另一部分的大小为n减1。
So the records and equalities, the records equalities on the running time of how a algorithm on such a data set always satisfies the following relation, T of n is equal to T of n minus 1 plus a linear term plus T of 0.
因此，记录和等式，算法在这样的数据集上的运行时间的记录等式总是满足以下关系，n的T等于n减去1加上线性项加T为0。
And we know already, so this is an unbalanced partition.
我们已经知道了，所以这是一个不平衡的分区。
We know the responds to the quadratic right in time so, which means that the running time of the quick sort algorithm a very simple array.
我们知道响应时间的二次权利，这意味着快速排序算法的运行时间是一个非常简单的数组。
So it contains all the elements of this array are equal.
所以它包含了这个数组的所有元素是相等的。
Which means that actually this array is already sorted.
这意味着实际上这个数组已经排序了。
In this array our quick sort algorithm spends a quadratic time to sort it to overcome this difficulty we'll do the following.
在这个数组中，我们的快速排序算法花费了一个二次时间来对其进行排序以克服这个困难，我们将执行以下操作。
Instead of partitioning our rate into two regions.
而不是将我们的速率划分为两个区域。
Namely these regions contain all elements that contain all x and all elements that are greater than x.
即这些区域包含包含所有x的所有元素以及大于x的所有元素。
We are going to partition into three parts.
我们将分为三个部分。
The corresponding partition procedure is usually called three-way partition.
相应的分区过程通常称为三向分区。
Formally, it returns two indices.
形式上，它返回两个指数。
m1 and m2, such that, all the elements inside the region from m1 to m2 are equal to x.
m1和m2，使得从m1到m2的区域内的所有元素都等于x。
All the elements to the left of this region are smaller than x.
该区域左侧的所有元素都小于x。
All the elements that are to the right of this region are greater than x.
该区域右侧的所有元素都大于x。
So this is how it looks pictorially.
所以这就是它的外观。
We have three regions.
我们有三个地区。
So, from l to m1 minus 1, we have all elements that are smaller than x.
因此，从l到m1减1，我们有所有小于x的元素。
In the region from m1 to m2, we have all elements that are equal to x.
在从m1到m2的区域中，我们拥有等于x的所有元素。
In the region from m2 plus 1 to r, we have all elements that are greater than x.
在从m2加1到r的区域中，我们拥有大于x的所有元素。
This procedure actually can be implemented in a similar way to their regional partition procedure.
实际上，此过程可以以与其区域分区过程类似的方式实现。
It can be implemented ties with a single kind of area with maintaing their regions or it can be implemented with two counts.
它可以通过维护其区域来实现与单一区域的联系，或者可以通过两个计数来实现。
So we first split our rate into regions which contain elements of most x or greater than x and then we split the region into two parts.
因此，我们首先将我们的速率分成包含大多数x或大于x的元素的区域，然后我们将该区域分成两部分。
Well, this is how the modified randomized quick sort algorithm is going to apply.
那么，这就是改进的随机快速排序算法将如何应用。
So we just replace it, the cold partition procedure by a cold two partition suite procedure.
所以我们只需用冷的两个分区套件程序替换它，冷分区程序。
Now we have three regions, and, actually the middle region is in its final place, so we do not touch it after the partition procedure.
现在我们有三个区域，实际上中间区域位于最终位置，所以我们在分区程序之后不要触摸它。
We make two recursive calls to the first region and to the last region.
我们对第一个区域和最后一个区域进行两次递归调用。
So, let's see whether the resulting algorithm is indeed Greek.
那么，让我们看看生成的算法是否确实是希腊语。
And for this, let's use the same visualization.
为此，让我们使用相同的可视化。
The resulting algorithm is shown here in the last column.
最终列中显示了生成的算法。
Let's, once again, run all the algorithms and see what happens in the last column.
让我们再次运行所有算法，看看最后一列中发生了什么。
Well we see that now, the results in Greek algorithm, is indeed Greek.
好吧，我们现在看到，希腊算法的结果，确实是希腊语。
------------- 48 -------------
06最后的评论
In this last video of the Quicksort lesson, I would like to address two implementation issues.
在Quicksort课程的最后一个视频中，我想解决两个实现问题。
So the first issue is about space complexity of the QuickSort algorithm.
所以第一个问题是关于QuickSort算法的空间复杂性。
So on one hand, when sorting an array by a Quicksort algorithm, we do not use any additional space.
因此，一方面，当使用Quicksort算法对数组进行排序时，我们不会使用任何额外的空间。
We just partition the array and with small elements inside the array.
我们只是对数组进行分区，并在数组中使用小元素。
On the other hand, the QuickSort algorithm is a recursive algorithm.
另一方面，QuickSort算法是递归算法。
And when we make a recursive call we store some information on this tech.
当我们进行递归调用时，我们会存储有关此技术的一些信息。
Right? So on one hand it is possible to show that the average recurrent depths is logarithmic.
对？因此，一方面可以证明平均复发深度是对数的。
Meaning that we need only a logarithmic additional space.
这意味着我们只需要一个对数的额外空间。
On the other hand, there is a very nice and elegant trick that allows to re-implement the QuickSort algorithm, such that it's worst case space complexity is at most logarithmic.
另一方面，有一个非常漂亮和优雅的技巧，允许重新实现QuickSort算法，这样它的最坏情况空间复杂度至多是对数。
So for this, let's recall that the QuickSort algorithm contains of the call to the partition procedure and then of two recursive calls.
因此，让我们回想一下，QuickSort算法包含对分区过程的调用，然后是两次递归调用。
So the situation when we have a recursive call is and, if the procedure is called tail recursion.
因此，当我们进行递归调用时的情况是，如果该过程被称为尾递归。
And there is a known way to eliminate such a recursive call.
并且有一种已知的方法可以消除这种递归调用。
Namely, instead of making this recursive call, let's just update.
也就是说，让我们只是更新，而不是进行这种递归调用。
Well, in the second recursive call, we sort the right part of our array.
好吧，在第二次递归调用中，我们对数组的正确部分进行排序。
I mean, the part from index n+1 to index r.
我的意思是，从索引n + 1到索引r的部分。
Instead of making this recursive call, let's replace the with a while loop, inside this while loop we call the partition procedure as shown on the slide.
不要进行这种递归调用，而是使用while循环替换，在while循环中我们调用分区过程，如幻灯片所示。
Then we make a recursive call to the left part, but instead of making the recursive call for the right part, we'll just update the value of l to be equal to m+1.
然后我们对左边部分进行递归调用，但是我们只是将l的值更新为等于m + 1，而不是对正确的部分进行递归调用。
And then we go to the beginning of this while loop, and this essentially mimics our recursive call.
然后我们转到这个while循环的开头，这基本上模仿了我们的递归调用。
So far so good.
到现在为止还挺好。
We've just realized that we can eliminate the last recursive call.
我们刚刚意识到我们可以消除最后一次递归调用。
At the same time let's also realize the following thing.
同时让我们也意识到以下事情。
In our QuickSort algorithm we first call the partition precision, then we make two recursive calls.
在我们的QuickSort算法中，我们首先调用分区精度，然后我们进行两次递归调用。
And these two recursive calls are in a sense independent.
而这两个递归调用在某种意义上是独立的。
Well it doesn't matter which comes first, right? So they do not depend on each other.
嗯先到哪个都没关系，对吧？所以他们不相互依赖。
This means that we can as well eliminate a recursive call through the first part.
这意味着我们也可以通过第一部分消除递归调用。
Well, and this in turn means that we can always select which one to eliminate.
好吧，这反过来意味着我们总能选择消除哪一个。
And for us, it is better to remove a recursive call to a longer part.
对我们来说，最好删除对较长部分的递归调用。
And this is why, if we always make a recursive call during the rate which is shorter, then we make a recursive call during the rate which is at least twice shorter than the initial already, right? And this in turn means that the depths of our recursion will be at most logarithmic.
这就是为什么，如果我们总是在较短的速率期间进行递归调用，那么我们在速率期间进行递归调用，该速率至少比初始速率短两倍，对吧？而这反过来意味着我们递归的深度将是最多的对数。
Because well, the first recursive call is made for an array of size of at most n over 2, then at most n over 4 and so on.
因为，第一次递归调用是针对一个大小最多n超过2的数组，然后最多n超过4，依此类推。
So the depth is logarithmic, which is good.
所以深度是对数的，这是好的。
And this can be implemented as follows.
这可以实现如下。
So we first call the partition procedure.
所以我们先调用分区程序。
It gives us a value of m.
它给出了m的值。
At this point, we know the length of two parts.
在这一点上，我们知道两个部分的长度。
And we just compare them.
我们只是比较它们。
If, for example, the lengths of the first part is shorter, then we make a recursive call to this part.
例如，如果第一部分的长度较短，那么我们对该部分进行递归调用。
And instead of making the recursive call for the second part, we just update the value of l.
而不是对第二部分进行递归调用，我们只更新l的值。
In the other case when the right part is shorter, we make the recursive call for this part, and instead of making the recursive call for this part, we'll just update the value of r.
在另一种情况下，当右边部分较短时，我们对这部分进行递归调用，而不是对这部分进行递归调用，我们只是更新r的值。
Right? So overall this gives us an implementation of the QuickSort algorithm which uses in the worst case an additional logarithmic space.
对？总的来说，这为我们提供了QuickSort算法的实现，该算法在最坏的情况下使用了额外的对数空间。
So the next implementation issue concerns the random bits used by our algorithm.
因此，下一个实现问题涉及我们的算法使用的随机位。
So I assume that we would like to have a deterministic version of our randomized QuickSort.
所以我假设我们想要一个随机化QuickSort的确定性版本。
And this is a reasonable thing to want because in practice we would like to have such a thing as reproducibility, which is for example essential for debugging.
这是一个合理的想法，因为在实践中我们希望有一个可重复性的东西，这对于调试来说是必不可少的。
So we would like our program to always output the same, on the same dataset.
因此，我们希望我们的程序始终在同一数据集上输出相同的内容。
And this is why we would probably not like to use random numbers, okay? Then we can do the following.
这就是为什么我们可能不想使用随机数，好吗？然后我们可以做到以下几点。
The following algorithm is known as intro sort and is used in many practical implementation of QuickSort.
以下算法称为简介排序，用于QuickSort的许多实际实现。
So instead of selecting the pivot element randomly, let's select it as follows using, for example, the following simple heuristic.
因此，不要随机选择pivot元素，而是使用例如以下简单的启发式方法选择它。
Each time when we're given a summary, and we need to partition it with respect to some pivot.
每当我们得到摘要时，我们需要根据某个支点对其进行分区。
So for this we need to select pivot, and let's select it as follows.
因此，我们需要选择pivot，然后按如下方式选择它。
We take the first element of the summary, the last element and the middle element, for example.
例如，我们采用摘要的第一个元素，最后一个元素和中间元素。
Then we have three elements, and we sort them.
然后我们有三个元素，我们对它们进行排序。
We just compare them and we select the medium value of these.
我们只是比较它们，然后选择它们的中值。
And we use this element as our pivot element.
我们使用这个元素作为我们的枢轴元素。
So this is a very simple heuristic, it can be implemented very efficiently.
所以这是一个非常简单的启发式方法，它可以非常有效地实现。
We just need three comparisons to select this median.
我们只需要三次比较来选择这个中位数。
And in many cases this is enough for the QuickSort algorithm to work effectively.
在许多情况下，这足以使QuickSort算法有效地工作。
However, this is not what we want, right.
但是，这不是我们想要的，对吧。
We are not happy with the statement that this algorithm works.
我们对此算法有效的说法不满意。
Works well in many cases.
在许多情况下效果很好。
We would like our algorithm to works well just on every possible input.
我们希望我们的算法能够很好地适用于所有可能的输入。
Unfortunately there are pathological cases in which these heuristics works badly.
不幸的是，存在这些启发式工作严重的病态案例。
But we can overcome this in the following way.
但我们可以通过以下方式克服这个问题。
While running our QuickSort algorithm, well let's count what is the current depths of our recursion three.
在运行我们的QuickSort算法时，让我们计算三次递归的当前深度。
And at some point when it exceeds some values here again, for some constant c, then we just stop the current algorithm and switch to some other algorithm.
并且在某些时候，当它再次超过某些值时，对于某些常数c，那么我们只需停止当前算法并切换到其他算法。
For example for the heap sort algorithm.
例如，对于堆排序算法。
This is another efficient algorithm, which is, asymptotically as good as MergeSort I mean, it has asymptotic again.
这是另一种有效的算法，它渐渐地和MergeSort一样好，我的意思是它再次渐近。
However Greek sort is usually faster in practice.
然而，希腊排序通常在实践中更快。
So, at this point, we switch to the quick sort algorithm.
所以，在这一点上，我们切换到快速排序算法。
Which means that for these pathological bad instances, for the QuickSort with this simple heuristic of selecting the pivot element, we still work in the worst case in time n log m.
这意味着对于这些病态的不良实例，对于使用这种简单的启发式选择枢轴元素的QuickSort，我们仍然在最坏的情况下工作n log m。
Because before we exceeded the depth c log n, we spend time n log m.
因为在超过深度c log n之前，我们花费时间n log m。
And after this, we'll start this algorithm.
在此之后，我们将启动此算法。
Immediately and we run the heap sort algorithm.
我们立即运行堆排序算法。
So overall, we've spent time n log n.
总的来说，我们花了时间n log n。
So this gives us an algorithm which in many cases performs like the QuickSort algorithm and in any case, just in the worst case, its running time is bounded above by n log n.
因此，这为我们提供了一种算法，在许多情况下，它像QuickSort算法一样执行，在任何情况下，只是在最坏的情况下，它的运行时间超过n log n。
So to conclude, the QuickSort algorithm is a comparison based algorithm whose running time is big O of n log n in the average case, and big O of n squared in the worst case.
总而言之，QuickSort算法是一种基于比较的算法，其运行时间在平均情况下为n log n的大O，在最坏的情况下为n的大O平方。
What is important in this algorithm is that it is very efficient in practice.
该算法的重要之处在于它在实践中非常有效。
It is more efficient than the north shore algorithim for example.
例如，它比北岸算法更有效。
For this reason it is commonly used in practice and for this reason it is called QuickSort
出于这个原因，它通常在实践中使用，因此称为QuickSort
------------- 49 -------------
01改变问题
Before recording this lecture, I stopped by the coffee shop.
在录制这个讲座之前，我在咖啡店停了下来。
This cappuccino is good.
这卡布奇诺很好吃。
And as soon as I gave $5 to the cashier, she faced an algorithmic problem of which coins to select to give me the change.
当我给收银员5美元时，她遇到了一个算法问题，哪个硬币可以选择给我改变。
And cashiers all over the world use an algorithmic approach called greedy algorithm to solve this problem.
世界各地的收银员都使用称为贪婪算法的算法来解决这个问题。
Today we will learn how cashiers and computer scientists use greedy algorithm for solving many practical problems.
今天我们将了解收银员和计算机科学家如何使用贪婪算法来解决许多实际问题。
So the change problem is finding the minimum number of coins needed to make change.
因此，变化问题是找到进行变更所需的最小硬币数量。
More formally, input to the problem is integer money and positive integers, coin1, coin2, coind, that represents coin denominations.
更正式地说，问题的输入是整数货币和正整数，coin1，coin2，coind，它代表硬币面额。
For example in the US, coin1 will be 1 cents, coin2 will be 5 cents, 10 cents, 25 cents, and 50 cents.
例如在美国，coin1将是1美分，coin2将是5美分，10美分，25美分和50美分。
And the output is the minimum number of coins, with denominations coin1, coin2, coind that changes money exactly.
并且输出是最小数量的硬币，面值coin1，coin2，coind可以准确地改变金钱。
So today in the morning, when cashier had to return me 40 cents, she most likely used the following algorithm.
所以今天早上，当收银员不得不给我40美分时，她很可能使用了以下算法。
First, finding the largest coin denomination that is smaller than 40 cents.
首先，找到小于40美分的最大硬币面额。
It will be 25 cents.
这将是25美分。
So she gave me 25, 15 cents left and then the next challenge is how to change 15 cents.
所以她给了我25,15美分，接下来的挑战是如何改变15美分。
The next step is she probably found the largest coin smaller than 15 cents, it is 10 cents.
下一步是她可能发现小于15美分的最大硬币，它是10美分。
She gave me 10 cents, and finally, she returned 5 cents.
她给了我10美分，最后，她还给了我5美分。
As a result, she changed 40 cents as 25 plus 10 plus 5.
结果，她改变了40美分，25加10加5。
Do you think it's the minimum number of coins she could possibly return? It is the minimal number of coins in the United States.
你认为这是她可能返回的最小硬币数量吗？这是美国最小的硬币数量。
But if you travel to Tanzania, it won't be the minimum number of coins because there is a 20 cent coin in Tanzania.
但如果你前往坦桑尼亚，它将不是最低数量的硬币，因为在坦桑尼亚有一个20美分硬币。
And therefore this greedy approach to solving the change problem will fail in Tanzania because there is a better way to change 40 cents, simply as 20 cents plus 20 cents, using Tanzanian 20 cents coin.
因此，这种解决变革问题的贪婪方法将在坦桑尼亚失败，因为使用坦桑尼亚20美分硬币有更好的方法可以改变40美分，简单地换20美分加20美分。
Since the greedy approach to solving the change problem failed, let's try something different.
由于解决变更问题的贪婪方法失败了，让我们尝试不同的东西。
Let's try the recursive algorithm for solving the same problem.
让我们尝试使用递归算法来解决同样的问题。
Suppose we want to change 9 cents, and our denominations are 1 cent, 5 cents, and 6 cents.
假设我们想要改变9美分，我们的面额是1美分，5美分和6美分。
What would be the optimal way to change 9 cents? Well, if we only knew what is the optimal ways to change 9 minus 6 cents, 9 minus 5 cents and 9 minus 1 cents, then we would know, what is the optimal way to change 9 cents? In other words, to change 9 cents, we need to know how to change small number of cents, in our case, 3 cents, 4 cents, and 8 cents.
改变9美分的最佳方式是什么？好吧，如果我们只知道改变9减6美分，9减5美分和9减1美分的最佳方法是什么，那么我们就知道，改变9美分的最佳方法是什么？换句话说，要改变9美分，我们需要知道如何改变少量美分，在我们的例子中，3美分，4美分和8美分。
And therefore, an approach to solving this problem would be to use this recurrence to write the recursive program.
因此，解决此问题的方法是使用此重复来编写递归程序。
This idea is implemented in the program RecursiveChange.
这个想法在程序RecursiveChange中实现。
To change money, cents using coins, coin1, coin2, coind, we do the following.
要使用硬币，coin1，coin2，coind来换钱，我们会做以下事情。
We first recursively call RecursiveChange with the amount of money, money minus coin1, money minus coin2, and money minus coind.
我们首先递归调用RecursiveChange的金额，金钱减去coin1，金钱减去coin2，金钱减去coind。
And find the minimum amount of money for these d choices.
并找到这些d选择的最低金额。
We have plus 1 because there is one more coin to add and returns this way.
我们加1，因为还有一个硬币可以添加并以这种方式返回。
This looks like the right approach to solve the problem, but let's check how fast the resulting program is.
这看起来是解决问题的正确方法，但让我们检查生成的程序的速度。
So, when we're changing 76 coins, there are actually three choices.
所以，当我们改变76个硬币时，实际上有三种选择。
We need to recursively call RecursiveChange for 70 cents, 71 cents, and 75 cents.
我们需要递归调用RecursiveChange 70美分，71美分和75美分。
But for each of these values, we need once again to call three choices.
但是对于这些价值中的每一个，我们都需要再次称之为三个选择。
And we will continue growing this tree and very quickly it will turn into a gigantic tree.
我们将继续种植这棵树，很快就会变成一棵巨大的树。
Let's check how many times we have already tried to change 70 cents.
让我们来看看我们已经尝试过多少次改变70美分。
Three times, and we only started expanding this tree.
三次，我们才开始扩展这棵树。
In fact, if we continue further, we will see that there were six times when we needed to compute RecursiveChange for 70.
事实上，如果我们继续进一步，我们将看到有六次我们需要计算RecursiveChange为70。
How many times do you think we will need to run recursive calls when we compute the minimal number of coins for 30 cents? It turn out that we will need to call it trillions of times, which means that our seemingly very elegant RecursiveChange program will not finish before the end of your lifetime.
当我们计算30美分的最小硬币数量时，您认为我们需要多少次才能运行递归调用？事实证明，我们需要将它称之为数万亿次，这意味着我们看似非常优雅的RecursiveChange程序将无法在您的生命周期结束之前完成。
So as simple as the change problem looks like, neither a greedy approach nor a recursive approach solve it in a reasonable time.
因此，就像变化问题一样简单，贪婪方法和递归方法都不能在合理的时间内解决。
60 years ago, a brilliant mathematician, Richard Bellman, had a different idea.
60年前，一位才华横溢的数学家理查德贝尔曼有一个不同的想法。