1.8「Stanford Algorithms」Merge So

So, the correct answer is the third one.

So, first of all, at a given level, j, there's precisely two to the j distinct sub-problems.

There's one outermost sub-problem at level zero, it has two recursive calls, those are the two, sub-problems at level one, and so on.

In general, since merge short calls itself twice, the number of sub-problems is doubling at each level, so that gives us the expression, two to the j, for the number of sub-problems at level j.

On the other hand, by a similar argument, the input size is halving each time.

With each recursive call you pass it half of the input.

That you were given.

So at each level of the recursion tree we're seeing half of the input size of the previous level.

So after J levels, since we started with an input size of N, after J levels, each sub-problem will be operating on an array of length N over two to the J.

Okay, so now let's put this pattern to use, and actually count up all of the lines of code that Merge Sort executes.

And as I said before, the key, the key idea is to count up the work level by level.

Now, to be clear, when I talk about the amount of work done at level J, what I'm talking about is the work done by those 2 to the J invocations of Merge Sort, not counting their respective recursive calls.

Not counting work which is gonna get done in the recursion, lower in the tree.

Now, recall, Merge Sort is a very simple algorithm.

It just has three lines of code.

First there is a recursive call so we're not counting that, second there is another recursive call again we're not counting that a little j and then third we just invoke the merge subroutine.

So really outside of the recursive calls all that merge sort does is a single invocation of merge.

Further recall we already have a good understanding of the number of lines of code that merge needs.

On an input of size m, it's gonna use, at most, 6m lines of code.

That's an analysis that we did in the previous video.

So, let's fix a level j.

We know how many sub-problems there are, two to the j.

We know the size of each sub-problem, n over two to the j, and we know how much work merge needs on such an input, we just multiply it by six, and then we just multiply it out, and we get the amount of work done at a level j.

'Kay? And all of the little adjacent problems.

So here it is in more detail.

Alright.

So.

We start with just the number of different sub-problems at level J and we just notice that, that was at most two to the J.

We also observe that each level J sub-problem is passed an, an array as input which has length N over two to the J.

And we know that the merge subroutine, when given an input, given an array of size, N over two to the J, will execute almost six times that many number of lines of code.

So to compute the total amount of work done at level J, we just multiply the number of problems times the work done sub-problem, per sub problem.

And then something sort of remarkable happens, where you get this cancellation of the two, two to the Js.

And we get an upper bound 6N.

Which is independent of the level J.

So we do at most six end operations at the root, we do at most six end operations at level one, at level two, and so on, okay? It's independent of the level.

Morally, the reason this is happening is because of a perfect equilibrium between two competing forces.

First of all, the number of subproblems is doubling with each.

Level of the recursion tree but 2ndly the amount of work that we do per sub-problem is halving with each level of the recursion tree's, once those two cancel out.

We get an upper bound 6N, which is independent of the level J.

Now, here's why that's so cool, right? We don't really care about the amount of work just at a given level.

We care about the amount of work that Merge Sort does ever, at any level.

But, if we have a bound on the amount of work at a level which is independent of the level, then our overall bound is really easy.

What do we do? We just take the number of levels, and we know what that is.

It's exactly log based two of N plus one.

Remember the levels are zero through log based two of N inclusive.

And then we have an upper bound 6N for each of those log n plus one levels.

So if we expand out this quantity, we get exactly the upper bound that was claimed earlier namely the number of operations merge sort executes is at most 6n times log base 2 of n plus 6n.

So that my friends, is a running time analysis of the merge sort algorithm.

That's why it's running time is bounded by a constant times N log N which, especially as N grows large, it is far superior to the more simple iterative algorithms like insertion or selection sort.

因此，正确的答案是第三个。

因此，首先，在给定级别j上，j个不同的子问题恰好有两个。

在级别0处有一个最外面的子问题，它有两个递归调用，分别是两个，在级别1处有子问题，依此类推。

通常，由于合并短调用自身两次，因此每个级别的子问题数量都会加倍，因此，对于级别j的子问题数量，我们可以将表达式j表示为两个。

另一方面，通过类似的论点，每次输入的大小减半。

对于每个递归调用，您将传递一半的输入。

那是给你的。

因此，在递归树的每个级别上，我们看到的是前一级别输入大小的一半。

因此，在J层之后，由于我们从N的输入大小开始，所以在J层之后，每个子问题都将在长度为N的数组上操作，长度为N到J的两倍。

好的，现在让我们使用此模式，并实际计算“合并排序”执行的所有代码行。

正如我之前说的，关键是，关键思想是逐级计算工作量。

现在，要明确一点，当我谈论在J层完成的工作量时，我所谈论的是这2个对Merge Sort的J调用所完成的工作，不计算它们各自的递归调用。

不计算递归中要完成的工作，在树的下面。

现在回想一下，合并排序是一种非常简单的算法。

它只有三行代码。

首先，有一个递归调用，所以我们不计此，其次，又有另一个递归调用，我们没有计入一个小j，然后，我们仅调用merge子例程。

因此，在递归调用之外，合并排序实际上只需要对合并进行一次调用。

进一步回想一下，我们已经对合并需求的代码行数有了很好的了解。

在大小为m的输入上，最多将使用6m行代码。

这是我们在上一个视频中所做的分析。

因此，让我们修复级别j。

我们知道有多少个子问题，两个到j。

我们知道每个子问题的大小，n等于j的2，并且知道这种输入需要多少工作合并，我们将其乘以6，然后乘以，就得到了在j级完成的工作。

“凯？和所有的小相邻问题。

所以这里更详细。

好的。

所以。

我们仅从J层的不同子问题的数量开始，我们只是注意到，这最多是J的两个。

我们还观察到每个级别J子问题都传递了一个数组作为输入，该数组的长度N超过J的两倍。

而且我们知道，当给定一个输入，给定一个大小为N的数组（比J大2）时，merge子例程将执行几乎六倍的代码行数。

因此，要计算在J级完成的工作总量，我们只需将问题数量乘以每个子问题的子问题完成的工作即可。

然后发生了一些了不起的事情，您将两个，两个J取消了。

我们得到一个上限6N。

独立于级别J。

因此，我们从根本上最多执行六个最终操作，在一级，二级执行最多六个最终操作，等等，好吗？它与级别无关。

在道德上，发生这种情况的原因是由于两个竞争力之间的完美平衡。

首先，每个子问题的数量加倍。

递归树的级别，但是第二，每个子问题我们要做的工作量都将递归树的每个级别减半，一旦这两个被取消。

我们得到一个上限6N，它独立于级别J。

现在，这就是为什么这么酷的原因吧？我们并不真正在乎给定级别的工作量。

我们关心合并排序在任何级别上所做的工作量。

但是，如果我们在一个独立于该级别的级别上对工作量进行限制，那么我们的总体限制确实很容易。

我们做什么？我们只考虑级别数，我们知道那是什么。

正是基于N加1的对数。

请记住，通过基于N的对数中的N（含两个），级别为零。

然后，对于每个log n加一个级别，我们有一个上限6N。

因此，如果我们扩展此数量，我们将确切地得到之前声称的上限，即合并排序执行的操作数最多为n的对数基数2加6n的6n倍。

以便我的朋友们，是对合并排序算法的运行时分析。

这就是为什么它的运行时间受常数N log N限制的原因，尤其是当N变大时，N log N远远优于更简单的迭代算法（如插入或选择排序）。