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.
但是首先讓我們回想一下主方法的內(nèi)容捐下。
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.
因此账锹，主方法將特定格式的重復(fù)出現(xiàn)作為輸入，特別是由三個不同的常數(shù)A坷襟，B和D歸類的重復(fù)出現(xiàn)奸柬。
A refers to the number of recursive calls, or the number of sub-problems that get solved.
A指的是遞歸調(diào)用的數(shù)量，或要解決的子問題的數(shù)量啤握。
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是在遞歸調(diào)用之外完成的工作的運行時間的指數(shù)。
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蹲蒲，子問題的數(shù)量乘以解決每個子問題所需的時間番甩，即N相對于B的T。
Cuz the input size of a subproblem is a number B + O of N to the D.
因為子問題的輸入大小是D的B + O N的個數(shù)届搁。
The work outside of the recursive calls.
遞歸調(diào)用之外的工作缘薛。
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.
因此宴胧，一旦問題大小[聽不清]降到特定常數(shù)以下，那么就不再需要遞歸表锻，您可以立即解決問題氢橙，即在固定時間內(nèi)解決問題地来。
No, given a recurrence in this permitted format, the running time is given.
否，如果以這種允許的格式重復(fù)出現(xiàn)铛嘱，則會給出運行時間古胆。
By one of three formulas.
通過三個公式之一喊儡。
Depending on the relationship between A.
取決于A之間的關(guān)系愚臀。
The number of [inaudible] calls.
[聽不清]呼叫的數(shù)量科雳。
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.
主方法的情況之一是蕾域，當(dāng)這兩個量相同時拷肌，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.
在第二種情況下，遞歸調(diào)用的數(shù)量a嚴(yán)格小于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懈万，當(dāng)a大于d的b大于b時拴清，我們得到了n的o的看起來有點時髦的運行時間，將其提高到對數(shù)冪的基數(shù)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.
讓我們從一個已經(jīng)知道答案的節(jié)奏開始木张，我們已經(jīng)知道運行時間。
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方法最重要的是確定三個相關(guān)事件參數(shù)A，B和D的值郊闯，然后就完成了妻献。
We just plug them in then we get the answer.
我們只需將其插入，即可得到答案团赁。
So A remember is the numbr of recursive calls.
因此育拨，請記住遞歸調(diào)用的數(shù)量。
So in merge sort recall we get two recursive calls.
因此欢摄，在合并排序回想中熬丧，我們得到兩個遞歸調(diào)用。
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.
好吧锹引，我們遞歸于數(shù)組的一半，因此子問題的大小是原始數(shù)組大小的一半唆香。
So B is equal to two.
因此B等于2嫌变。
And recall that outside of the recursive calls all merge sort does is merge.
并請記住，在遞歸調(diào)用之外躬它，所有合并排序所做的都是合并腾啥。
And that's a linear time subroutine.
這是一個線性時間子程序。
So exponent D is one reflection of factor with linear time.
因此冯吓，指數(shù)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之間的關(guān)系的關(guān)鍵觸發(fā)器组贺。
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.
現(xià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.
當(dāng)然，我們已經(jīng)知道了哪一個择诈。
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.
好的械蹋？但這至少是一項健全性檢查，主要方法至少是要確認(rèn)我們已經(jīng)通過直接手段證明的事實吭从。
So let's look at a second example.
因此朝蜘，讓我們看第二個例子。
The second example is going to be for the binary search [inaudible] in a sorted array.
第二個示例將用于排序數(shù)組中的二進(jìn)制搜索[聽不清]涩金。
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.
現(xiàn)在我們還沒有明確討論二進(jìn)制搜索谱醇，我也不打算討論，因此步做，如果您不知道什么是二進(jìn)制搜索副渴，請在教科書中閱讀或直接在網(wǎng)絡(luò)上查找，容易找到描述全度。
But the upshot is, this is basically how you'd look up a phone number in a phone book.
但是結(jié)果是煮剧，這基本上就是您在電話簿中查找電話號碼的方式。
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.
現(xiàn)在将鸵，我意識到這部視頻的最年輕的觀看者實際上并沒有使用物理電話簿的經(jīng)驗勉盅，而是為其余的人。
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.
然后移袍，根據(jù)要查找的元素是大于還是小于中間元素，根據(jù)需要在左側(cè)或右側(cè)進(jìn)行遞歸老充。
Now the master method applies equally well to binary search and it tells us what its running time is.
現(xiàn)在葡盗，master方法同樣適用于二進(jìn)制搜索，并且告訴我們其運行時間是多少啡浊。
So in the next quiz, you'll go through that exercise.
因此戳粒，在下一個測驗中路狮，您將完成該練習(xí)。
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]
