-
I haven't said how I'm going to get those sorted lists, but imagine I had two sorted lists like that.
我还没有说明我怎么才能得到已排序的列表,但是想像一下我现在已经有,两个已排序好序的列表了。
-
When these two merges are done, we're basically at a stage in that branch where we can now merge those two together, which gives us that, and it goes through the rest of it.
拿到从那边得到的第二个子列表，这是一个基本情况,合并它，当这两个合并完成后，我们基本到了该分支阶段，这里我们可以把两个合并在一起。
-
Well, it looks like it took 1 in this case or it involves-- we can put it another way, merging those two lists involved looking at two numbers, 1, 2, and that's it.
在这种情况下看起来只用了1次-,我们可以从另一个角度看，合并这两个列表涉及到了,2个数字，1，2，就是这样。
-
Run merge sort on those. By induction, if it does the right thing, I'm going to get back two lists, and I'm going to then merge Them together. Notice what I'm going to do.
在这些上面再运行归并排序，根据归纳，如果这样是正确的,我将重新得到两个列表,然后我会把它们合并在一起。
-
So when I do the analysis, I want to think about what am I doing here, am I capturing all the pieces of it? Here, the two variables that matter are what's the length of the list, and how many times I'm going to search it?
这里，要关注的,两个变量是列表,的长度以及我要搜索的次数,这种情况下，这个算法赢了？
-
I'm walking along the list once, taking two things and saying, make sure the biggest one is next.
我遍历一次列表，每次取两个值,确认最大的元素在后面一个。
-
So let me give you an example. Suppose I want to merge two lists, and they're sorted.
我想合并两个列表,并且这两个列表已经排好序了。
-
So at the moment left hand is at the start of this list of size 1, my right hand is at the start of this list of size 1, and now I need to merge these two lists.
现在左手手指指向这个大小为1的列表的开始,右手手指指向这个大小为1的列表的开始,现在我需要合并这两个列表。
-
Let's assume that I could somehow get to the stage where I've got two sorted lists.
让我们来假设目前的情况是：,我已经有两个已排好序的列表。
-
If there are less than two elements there I just check one or both of those to see if I'm looking for the right thing.
列表里是否剩余超过两个元素？,是否剩余不足两个元素,这里面我就挑一两项来检查下是否运行正常。
-
Wow I can sort two lists, so I can merge two lists.
喔，我可以，将两个列表排好序。
-
So now I have to merge these two lists of size 2.
现在我需要合并这两个各有2个元素的列表。
-
I said it poorly. What's the point?
那么我就可以将两个列表进行合并了？
-
I'll let you just grok it but you can see it's basically doing what I did over there. Setting up two indices for the two sub-list,it's just walking down, finding the smallest element, putting it into a new list. When it gets to the end of one of the lists, it skips to the next part, and only one of these two pieces will get called because only one of them is going to have things leftovers.
你们可以大体的浏览一下,但是它们基本就是我在那里所做的事情,为两个子列表设置了两个指针,指针顺着列表走下去，找到最小的元素,把它放入到一个新的列表中去,当它走到一个列表的尾部时,它会跳到下部分去,两部分中只有一个会被执行,因为只有一个会有元素剩余。
-
Down here, I've just got two things to merge, and then I've got things of size two to merge and then things of size four to merge. But notice a trade off. I have n operations if you like down there of size one.
但是n的大小是不同的，是吗？在这里我们只要合并两个元素,然后是合并长度为2的列表,接下来是合并长度为4的列表,但是观察一下之间的权衡关系。
-
STUDENT: PROFESSOR: In both lists, right.
学生：【难以理解中】,教授：在两个列表中，这是线性的，O的。
应用推荐