In this video, we'll be giving a running time analysis of the merge sort algorithm.
In particular, we'll be substantiating the claim that the recursive divide and conquer merge sort algorithm is better, has better performance than simpler sorting algorithms that you might know, like insertion sort, selection sort, and bubble sort.
So, in particular, the goal of this lecture will be to mathematically argue the following claim from an earlier video, that, in order to sort an array in numbers, the merge sort algorithm needs no more than a constant times N log N operations.
That's the maximum number of lines of executable code that will ever execute specifically six times n log n plus six n operations.
So, how are we going to prove this claim? We're going to use what is called a recursion tree method.
The idea of the recursion tree method is to write out all of the work done by the recursive merge sort algorithm in a tree structure, with the children of a given node corresponding to the recursive calls made by that node.
The point of this tree structure is it will facilitate, interesting way to count up the overall work done by the algorithm, and will greatly facilitate, the analysis.
So specifically, what is this tree? So at level zero, we have a root.
And this corresponds to the outer call of Merge Sort, okay? So I'm gonna call this level zero.
Now this tree is going to be binary in recognition of the fact that each indication of Merge Sort makes two recursive calls.
So the two children will correspond to the two recursive calls of Merge Sort.
So at the route, we operate on the entire input array, so let me draw a big array indicating that.
And at level one, we have one sub problem for the left half, and another sub problem for the right half of the input array.
And I'll call these first two recursive calls, level one.
Now of course each of these two level one recursive calls will themselves make two recursive calls.
Each operating on then a quarter of the original input array.
So those are the level two recursive calls, of which there are four, and this process will continue until eventually the recursion bottoms out, in base cases when they're only an array size zero or one.
So now I have a question for you which I'll, I'll give you in the form of a quiz which is, at the bottom of this recursion tree corresponding to the base cases, what is the level number at the bottom? So, at what level do the leaves in this tree reside?
在本视频中，我们将对合并排序算法进行运行时分析。
特别是，我们将证实这样一种说法，即递归的“分而治之”合并排序算法更好，并且比您可能知道的简单排序算法（例如插入排序，选择排序和冒泡排序）具有更好的性能。
因此，特别是，本讲座的目标是从早期的视频中对以下主张进行数学辩论，即为了对数组进行数字排序，合并排序算法所需的时间不超过常数N log N个运算。
这是将执行的特定n行n log n加六n次操作的最大次数的可执行代码。
那么，我们将如何证明这一主张？我们将使用所谓的递归树方法。
递归树方法的思想是将递归合并排序算法以树形结构写出的所有工作，给定节点的子代对应于该节点进行的递归调用。
这种树结构的要点是它将方便，有趣地计算该算法完成的全部工作，并且将极大地方便分析。
那么，这棵树到底是什么？因此，在零级，我们有一个根。
这对应于Merge Sort的外部调用，好吗？所以我将这个级别称为零。
现在，由于合并排序的每个指示都会进行两次递归调用，因此该树将是二叉树。
因此，这两个子项将对应于Merge Sort的两个递归调用。
因此，在该路线上，我们对整个输入数组进行操作，因此让我绘制一个大数组来表明这一点。
在第一级，输入数组的左半部分有一个子问题，输入数组的右半部分有另一个子问题。
我将把这两个递归调用称为第一级。
当然，现在这两个一级递归调用中的每一个本身都会进行两个递归调用。
然后，每个操作都将占原始输入数组的四分之一。
因此，这些是第二级递归调用，其中有四个递归调用，在基本情况下，当它们只是一个数组大小为零或一时，此过程将继续进行直到最终递归结束。
所以现在我有一个问题要问，我将以测验的形式给您，在与基本案例相对应的此递归树的底部，底部的级别号是多少？那么，这棵树的叶子位于什么级别？
Question
网友评论