1.8「Stanford Algorithms」Merge So

Okay, so hopefully you guess,correctly guess, that the answer is the second one, so namely that the number of levels of the recursion tree is essentially logarithmic in the size of the input array.

The reason is basically that the input size is being decreased by a factor two with each level of the recursion.

If you have an input size of N at the outer level, then each of the first set of recursive calls operates on array of size n over two, at level two, each array has size n over four, and so on.

Where does the recursion bottom out? Well, down at the base cases where there's no more recursion, which is where the input array has size one or less.

So in other words, the number of levels of recursion is exactly the number of times you need to divide N by two, until you get down to a number that's most one.

Recall that's exactly the definition of a logarithm base two of n.

So since the first level is level zero and last level is level log base two of n.

The total number of levels is actually log base two of n plus one.

And when I write down this expression, I'm here assuming that N is a, is a power of two.

Which is not a big deal.

I mean the analysis is easily extended to the case where N is not a power of two.

And this way, we don't have to think about fractions.

Log base two of N then is an integer.

Okay so let's return to the recursion tree.

Let me just redraw it really quick.

So again, down here at the bottom of the tree we have the leaves, i.e. The base cases where there's no more recursion.

Which when N is the power of two correspond exactly to single element arrays.

So that's the recursion tree corresponding to an indication of Merge Sort.

And the motivation for writing down, for organizing the work performed by Merge Sort in this way, is it allows us to count up the work, level by level.

And we'll see that that's a particularly convenient way to account for all of the different lines of code that get executed.

Now, to see that in more detail, I need to ask you to identify a particular pattern.

So, first of all, the first question is, at a given level, j, of this recursion, exactly how many distinct sub-problems are there, as a function of the level j? That's the first question.

The second question is, for each of those distinct sub-problems at level j, what is the input size? So, what is the size of the a-, of the array, which is passed to a sub-problem residing at level j of this recursion tree.

好的，所以希望您能正确地猜出答案是第二个答案，也就是说，递归树的级别数实质上是输入数组大小的对数。

原因基本上是，递归的每个级别的输入大小都减小了两倍。

如果外部级别的输入大小为N，则第一组递归调用中的每一个都对大小为2的n数组进行操作，在级别2上，每个数组的大小为4的n数组，依此类推。

递归在哪里触底？好吧，在没有更多递归的基本情况下，输入数组的大小等于或小于1。

因此，换句话说，递归级别的数量恰好是您需要将N除以2的次数，直到得出的数字最大为止。

回想一下，这正是n以2为底的对数的定义。

因此，由于第一个级别是零级别，最后一个级别是n的对数第二级别。

级别的总数实际上是n加1的对数二。

当我写下这个表达式时，我在这里假设N是a，是2的幂。

没什么大不了的。

我的意思是，分析很容易扩展到N不是2的幂的情况。

这样，我们就不必考虑分数。

N的对数以2为底的整数。

好的，让我们回到递归树。

让我快速重绘它。

再次，在树的底部，这里有叶子，即不再进行递归的基本情况。

当N是2的幂时，它恰好对应于单个元素数组。

这就是与“合并排序”指示相对应的递归树。

写下，组织Merge Sort进行的工作的动机是，它使我们能够逐级计算工作量。

我们将看到，这是解决所有已执行代码行的特别方便的方法。

现在，要更详细地了解这一点，我需要请您确定一个特定的模式。

因此，首先，第一个问题是，在给定级别j上，此递归根据级别j到底有多少个不同的子问题？那是第一个问题。

第二个问题是，对于级别j的每个不同子问题，输入大小是多少？因此，数组的a-的大小是多少，传递给位于此递归树的j级的子问题。