In this video we'll put the master method to use by instantiating it for six different examples.
在本视频中，我们将通过实例化六个不同的示例来使用master方法。
But first let's recall what the master method says.
但是首先让我们回想一下主方法的内容。
So the master method takes as input recurrences of a particular format, in particular recurrences that are paramerized by three different constants, A, B and D.
因此，主方法将特定格式的重复出现作为输入，特别是由三个不同的常数A，B和D归类的重复出现。
A refers to the number of recursive calls, or the number of sub-problems that get solved.
A指的是递归调用的数量，或要解决的子问题的数量。
B is the factor by which the sub-problem size is smaller than the original problem size.
B是子问题大小小于原始问题大小的因素。
And D is the exponent in the running time of the work done outside of the recursive calls.
D是在递归调用之外完成的工作的运行时间的指数。
So the recurrence has the form T of N.
因此，递归的形式为N的T。
The running time [inaudible] put up [inaudible], N is no more than A, the number of subproblems, times the time required to solve each subproblem, which is T of N over B.
运行时间[听不清]成立[听不清]，N不超过A，子问题的数量乘以解决每个子问题所需的时间，即N相对于B的T。
Cuz the input size of a subproblem is a number B + O of N to the D.
因为子问题的输入大小是D的B + O N的个数。
The work outside of the recursive calls.
递归调用之外的工作。
There's also a base case, which I haven't written down.
还有一个基本案例，我还没有写下来。
So once the problem size [inaudible], drops below a particular constant, then there should be no more recursion, and you can just solve the problem immediately, that is in constant time.
因此，一旦问题大小[听不清]降到特定常数以下，那么就不再需要递归，您可以立即解决问题，即在固定时间内解决问题。
No, given a recurrence in this permitted format, the running time is given.
否，如果以这种允许的格式重复出现，则会给出运行时间。
By one of three formulas.
通过三个公式之一。
Depending on the relationship between A.
取决于A之间的关系。
The number of [inaudible] calls.
[听不清]呼叫的数量。
And B raised to the D power.
并且B提升到D的力量。
Case one of the master method is when these two quantities are the same, A equals B to the D.
主方法的情况之一是，当这两个量相同时，A等于D等于B。
Then the running time is N to the D log N.
那么运行时间是N到D logN。
No more than that.
仅此而已。
In case two, the number of recursive calls, a, is strictly smaller than b to the d.
在第二种情况下，递归调用的数量a严格小于d的b。
Then, we get a better running time upper-bound, of o of n to the d, and, when a is bigger than b to the d, we get this somewhat funky-looking running time of o of n, raised to the log base b of a power.
然后，我们得到了一个更好的运行时间上限，即d的n的o的o，当a大于d的b大于b时，我们得到了n的o的看起来有点时髦的运行时间，将其提高到对数幂的基数b。
We'll understand what that, where that formula comes from a little later.
我们稍后将了解该公式的来源。
So, that's the master method.
因此，这是主要方法。
It's a little hard to interpret the first time you see it, so let's look at some concrete examples.
第一次看时，很难解释一下，所以让我们看一些具体的例子。
Let's begin with an out rhythm that we already know the answer to, that we already know the running time.
让我们从一个已经知道答案的节奏开始，我们已经知道运行时间。
Namely let's look at merge short.
即让我们看一下合并短。
So again what's so great about the master method is all we have to do is identify the values of the three relevent parameters A, B, and D, and we're done.
因此，再次要掌握的master方法最重要的是确定三个相关事件参数A，B和D的值，然后就完成了。
We just plug them in then we get the answer.
我们只需将其插入，即可得到答案。
So A remember is the numbr of recursive calls.
因此，请记住递归调用的数量。
So in merge sort recall we get two recursive calls.
因此，在合并排序回想中，我们得到两个递归调用。
B is the factor by which the sub problem size is smaller than that in the original.
B是子问题大小小于原始问题大小的因素。
Well we recurse on half the array so the sub problem size if half that of the original.
好吧，我们递归于数组的一半，因此子问题的大小是原始数组大小的一半。
So B is equal to two.
因此B等于2。
And recall that outside of the recursive calls all merge sort does is merge.
并请记住，在递归调用之外，所有合并排序所做的都是合并。
And that's a linear time subroutine.
这是一个线性时间子程序。
So exponent D is one reflection of factor with linear time.
因此，指数D是线性时间因子的一种反映。
So remember the key trigger which determines which of the three cases is the relationship between A and B and the D.
因此，请记住确定这三种情况中哪一个是A和B与D之间的关系的关键触发器。
So A obviously is two.
因此，A显然是两个。
And B to the D is also equal to two.
并且B到D也等于2。
So this puts us in case one.
因此，这使我们处于第一种情况。
And remember in case one.
并记住第一种情况。
Now that the running time is bounded above by O of N to the D log N.
现在，运行时间由N的O限制为D logN。
In our case D equals one, so this is just O of N log N.
在我们的情况下，D等于1，所以这只是N log N的O。
Which of course, we already knew.
当然，我们已经知道了哪一个。
Okay? But at least this is a sanity check, the master method is at least reconfirming facts which we've already proven by direct means.
好的？但这至少是一项健全性检查，主要方法至少是要确认我们已经通过直接手段证明的事实。
So let's look at a second example.
因此，让我们看第二个例子。
The second example is going to be for the binary search [inaudible] in a sorted array.
第二个示例将用于排序数组中的二进制搜索[听不清]。
Now we haven't talked explicitly about binary search, and I'm not planning to, so if you don't know what binary search is please read about it in a textbook or just look it up on the web and it'll be easy to find descriptions.
现在我们还没有明确讨论二进制搜索，我也不打算讨论，因此，如果您不知道什么是二进制搜索，请在教科书中阅读或直接在网络上查找，容易找到描述。
But the upshot is, this is basically how you'd look up a phone number in a phone book.
但是结果是，这基本上就是您在电话簿中查找电话号码的方式。
Now I realize probably the youngest viewers of this video haven't actually had the experience of using a physical telephone book but for the rest of you.
现在，我意识到这部视频的最年轻的观看者实际上并没有使用物理电话簿的经验，而是为其余的人。
As you know, you don't actually start with the A's, and then go to the B's, and then go to the C's, if you're looking for a given name.
如您所知，如果您要查找给定名称，则实际上并没有以A开头，然后是B开头，然后是C开头。
You more sensibly split the telephone book in the middle.
您更明智地在中间拆分了电话簿。
[inaudible].
[听不清]。
Then you recurse on the left or the right half, as appropriate, depending on if the element you're looking for is bigger or less than the middle element.
然后，根据要查找的元素是大于还是小于中间元素，根据需要在左侧或右侧进行递归。
Now the master method applies equally well to binary search and it tells us what its running time is.
现在，master方法同样适用于二进制搜索，并且告诉我们其运行时间是多少。
So in the next quiz, you'll go through that exercise.
因此，在下一个测验中，您将完成该练习。
Examples - Question 1
Where are the respective values of a,b,d for a binary search of a sorted array, and which case of the Master Method does this correspond to ?
1,2,0 [Case 1]
1,2,1 [Case 2]
2,2,0 [Case 3]
2,2,1 [Case 1]
