The correct answer is the second one.
That if you have an array with no split inversions, then everything in the first half is less than everything in the second half.
Why? Well consider the contrapositive.
Suppose you had even one element in the first half which was bigger than any element in the second half.
That pair of element alone would constitute a split inversion.
Okay? So if you have no split inversions, then everything on the left is smaller than everything on the, in the right half of the array.
Now, more to the point, think about the execution of the merge subroutine on an array with this property.
On an input array A where everything in the left half is less than everything in the right half.
What is merge gonna do? All right, so remember it's always looking for whichever is smaller the first element of, remaining in B or the first element remaining in C, and that's what it copies over.
Well if everything in B is less than everything in C, everything in B is gonna get copied over into the [inaudible] ray D before C ever gets touched.
Okay? So merge had an unusually trivial execution on input arrays with no split inversions, with zero split inversions.
First it just goes through B and copies it over.
Then it just concatonates C.
Okay there's no interleaving between the two.
So no split inversions means nothing get copied from C until it absolutely has to, until B is exhausted.
So this suggests that perhaps copying elements over from the second subarray, C, has something to do with the number of split inversions in the original array, and that is, in fact, the case.
So we're gonna see a general pattern about copies from the second element C, second array C [inaudible] exposing split inversions in the original input array A.
So let's look at a more detailed example, to see what that pattern is.
Let's return to it, the example in the previous video.
Which is an array with six elements ordered one, three, five, two, four, six.
So we do our recursive call, and in fact, the left half of the array is sorted, and the right half of the array is already sorted.
So [inaudible] sorting what's gonna be done [inaudible] get to zero inversions for both our recursive calls.
Remember, in this example, it turns out all of the inversions are split inversions.
So, now let's trace through the merge sub-routine invoked on these two sorted sub-arrays, and try to spot a connection with the number of split inversions in the original 6-element array.
So, we initialize indices I and j to point to the first element of each of these sub-arrays.
So, this left one is b, and this right one is c and the output is d.
Now, the first thing we do, is we copy the one over from b into the upward array.
So, one goes there, and we advance this index over to the three.
And, here nothing really interesting happened, there's no.
Reason to count any split inversions, and indeed, the number one is not involved in any split inversions, cuz one is smaller than all of the other elements, and it's also in the first index.
Things are much more interesting, when we copy over the element two from the second array c.
And, notice at this point, we have diverged from the trivial execution that we would see with an array with no split inversions.
Now, we're copying something over from c, before we've exhausted copying d.
So we're hoping this will expose some split in versions.
So we copy over the two.
And we advance the second pointer J into C.
And the thing to notice is this exposes two split inversions.
The two split inversions that involve the element two.
And those inversions are three comma two and five comma two.
So why did this happen? Well, the reason we copied two over is because it's smaller than all the elements we haven't yet looked at in both B and C.
So in particular, two is smaller than the remaining elements in B, the three and the five.
But also because B is the left array.
The indices and the three and five have to be less than the index of this two, so these are inversions.
Two is further to the right than the original input array, and yet it's smaller than these remaining elements in B.
So there are two elements remaining in B, and those are the two split inversions that involve the element two.
So now, let's go back to the emerging subroutine, so what happens next? Well, next, we make a copy from the first array, and we sort of realize that nothing really interesting happens when we copy from the first array, at least with respect to split inversions.
Then we copy the four over, and yet again, we discover a split inversion, the remaining one which is five comma four.
Again, the reason is, given that four was copied over before, what's left in B, it's gotta be smaller than it, but by virtue of being in the rightmost array, it's also gotta have a bigger index.
So it's gotta be a split inversion.
And now the rest of the merge subroutine executes.
Without any real incident.
The five gets copied over and we know copies from the left array are boring.
And then we copy the six over and copies from the right array are generally interesting but not if the left array is empty.
That doesn't involve any split inversions.
And you will recall, from the earlier video that these were inversions in the original array, three:2, five:2, and five:4.
We discovered them all in automated method, by just keeping an eye out when we copy from the right array C.
So this is indeed a general principle, so let me state the general claim.
So the claim is not just in this specific example, and this specific execution, but no matter what the input array is, no matter how many split inversions there might be, the split inversions that involve an element of the second half of the array are precisely.
Those elements remaining in the first array when that element gets copied over to the output array.
So this is exactly what the pattern that we saw in the example.
What works on the right array.
In C, we had the elements two, four, and six.
Remember, every split inversion has to, by definition, involve one element from the first half, and one element from the second half.
So to count [inaudible] inversions, we can just group them according to which element of the second array there, did they involve.
So out of the two, four, and six, the two is involved in the splitter conversions, 3-2, and 5-2.
The three and the five were exactly the elements remaining in B.
Bit over two.
The split inversions involving four is exactly the inversion five four and five is exactly the element that was remaining in B when we copied over the four.
There's no split inversions involving six and indeed the element D was empty when we copied the six over into the output array D.
So what's the general argument? What's quite simple.
Lets just zoom in and fixate on a particular element, X that belongs to that first half of the array that's among the first half of the elements and let's just examine which Y's so which elements of the second array the second half of the original input array involve with split versions of X.
So there are two cases depending on whether X is copies to the output array D before or after Y now if X is copied to the output before Y well then since the [inaudible] in sorted order that means X has got to be shorter than Y so there's not going to be any split in inversion.
On the other hand, if y is copied to the output d before x, then again because we populate d left to right in sort order, that's gotta mean that y is less than x.
Now X.
Is still hanging out in the left array, so it has a less index than Y.
Y comes from the right array.
So this is indeed a split inversion.
So putting these two together it says that the.
Elements X.
Of the array B.
That form split inversions with Y.
Are precisely those that are going to get copied to the output array, after what? So, those are exactly the number of elements remaining in b, when y gets copied over.
So, that proves the general claim.
[sound] So, this slide was really the key insight.
Now that we understand exactly why, counting split inversions is easy.
As we're merging together two sorted sub-arrays, it's a simple matter to just translate this into code, and get a linear time implementation of a sub-routine that both merges and counts the number of split inversions.
Which, then, in the overall recursive algorithm, will have n log n running time, just as in merge sort.
So, let's just spend a quick minute filling in those details.
So.
I'm not gonna write out the pseudocode, I'm just going to write out what you need to augment the merge pseudocode, discussed a few slides ago, by, in order to count split inversions as you're doing the merging.
And this will follow immediately from the previous claim, which indicated how split inversions relate to, the number of elements remaining on the left array as you're doing the merge.
So, the idea is the natural one, as you're doing the merging, according to the previous pseudocode of the two sorted sub-arrays, you just keep a running total of the number of split inversions that you've encountered, all right? So you've got your sorted sub-array b, you've got your sorted sub-array c.
You're merging these into an output array D.
And as you traverse through D and K from one to N you just start the count at zero and you increment it by something each time you do a copy over from either from B or C.
So, what's the increment, well what did we just see? We saw the copies.
Involving B don't count.
We're not gonna look at split inversions when we copy over for B.
Only when we look at them from C, right? Every split inversion involves exactly one element from each of B and C.
So I may as well count them, via the elements in C.
And how many split inversions are involved with the given element of C? Well, it's exactly how many elements of B remain when it gets copied over.
So that tell us how to increment this running count.
And it falls immediately from the claim on the previous slide that this.
Implementation of this running total counts precisely the number of split inversions that the original input array A possesses.
And you'll recall that the left inversions are counted by the first recursive call, the right inversions are counted by the second recursive call.
Every inversion is either left or right or split, it's exactly one of those three types.
So with our three different subroutines, the two recursive ones and this one here we successfully count up all of the inversions of the original input array.
So that's the correctness of the algorithm, what's the running time? What we're calling merge sort, we begin by just analyzing the running time of merge and then we discuss the running time of the entire merge sort [inaudible].
Let's do the same thing here briefly.
So what's the running time of the [inaudible] team for this merging and simultaneously cutting into split versions.
Work that we do in the merging and we already know that that's linear and then the only additional work here is.
Incrementing this running count.
And that's constant time for each element of D, right? Each time we do a copy over, we do [inaudible], a single edition to our running count.
So constant time for element D, or linear time overall.
So I'm being a little sloppy here, sloppy in a very conventional way.
But it is a little sloppy about writing O of N plus O of N is equal to O of N.
Be careful when you make statements like that, right? So if you added O of N to itself N times, it would not be O of N.
But if you add O of N to itself a constant number of times, it is still O of N.
So you might, as an exercise, want to write out, a formal version of what this means.
Basically, there's some constant C [inaudible].
The merge step takes a C11 in steps.
There's a constant C2 so that the rest of the work is in those C2 times N steps.
So when we add them we get, get [inaudible] most quantity C1 plus C2 times N steps, which is still [inaudible] because C1 plus C2 is a constant.
Okay? So linear work for merge, linear work the running count, that's linear work in the subroutine overall.
And no by exactly the same argument we used in merge sort because we have two recursive calls on half the size and we do linear work outside of the cursive calls, the overall running time is O of N log N.
So we really just piggybacked on merge sort The constant factor a little bit to do the counting along the way, but the running time remains at the go of [inaudible].
正确的答案是第二个。
那就是，如果您有一个没有拆分反转的数组，那么上半年的所有内容都会少于下半年的所有内容。
为什么？好考虑相反。
假设您在上半年甚至有一个元素大于下半年的任何元素。
单单这对元素就构成了分裂反转。
好的？因此，如果没有拆分反转，则数组右半部分中的所有内容都小于其上的所有内容。
现在，更重要的是，考虑在具有此属性的数组上执行合并子例程。
在输入数组A上，左半部分的内容少于右半部分的内容。
合并将要做什么？好吧，所以请记住，它总是在寻找B中的第一个元素或C中的第一个元素较小的那个，这就是它要复制的内容。
好吧，如果B中的所有内容都小于C中的所有内容，那么B中的所有内容都将在C接触之前被复制到[听不清]射线D中。
好的？因此，merge在输入数组上执行的异常琐碎的操作没有拆分反转，拆分反转为零。
首先，它只是经过B并将其复制过来。
然后，它只是将C组合起来。
好的，两者之间没有交织。
因此，没有分割反转意味着从C复制任何内容，直到绝对必须复制为止，直到B用尽为止。
因此，这表明也许从第二个子数组C中复制元素可能与原始数组中拆分反转的数量有关，实际上就是这种情况。
因此，我们将看到有关第二个元素C，第二个数组C [听不清]的副本的一般模式，它暴露了原始输入数组A中的拆分反转。
因此，让我们看一个更详细的示例，看看该模式是什么。
让我们回到上一个视频中的示例。
这是一个具有六个元素的数组，它们的顺序分别为1、3、5、2、4、6。
因此，我们进行了递归调用，实际上，数组的左半部分已排序，而数组的右半部分已排序。
因此，[音频不清晰]排序将要完成的工作[音频不清晰]对我们的两个递归调用都归零。
请记住，在此示例中，事实证明所有反转都是拆分反转。
因此，现在让我们追溯在这两个排序的子数组上调用的merge子例程，并尝试找出原始6元素数组中拆分反转数目的连接。
因此，我们将索引I和j初始化为指向每个这些子数组的第一个元素。
因此，左边的那个是b，右边的那个是c，输出是d。
现在，我们要做的第一件事是将一个从b复制过来的复制到向上数组中。
因此，一个去了那里，我们将该指数提高到了三个。
而且，这里没有真正有趣的事情发生，没有。
计数任何拆分反转的原因，实际上，任何拆分反转均不涉及数字，因为cuz小于所有其他元素，并且它也在第一个索引中。
当我们从第二个数组c复制元素2时，事情会变得更加有趣。
而且，请注意，在这一点上，我们与在没有拆分反转的数组中看到的琐碎执行有所不同。
现在，我们要从c复制一些内容，然后再用尽d的复制。
因此，我们希望这会暴露一些版本上的差异。
因此，我们复制了两个。
然后我们将第二个指针J移到C中。
需要注意的是，这暴露了两个分裂的反转。
涉及元素二的两个拆分反演。
这些反演是三个逗号2和五个逗号2。
那么为什么会这样呢？好吧，我们之所以复制两个，是因为它比我们尚未在B和C中查看过的所有元素都小。
因此，尤其是两个要小于B中的其余元素，三个和五个。
也是因为B是左数组。
索引以及三个和五个必须小于这两个的索引，因此它们是反转的。
比原始输入数组靠右的两个，但比B中其余的这些元素小。
因此，B中剩余两个元素，而这两个是涉及元素2的拆分反演。
现在，让我们回到新兴的子例程，接下来会发生什么？好吧，接下来，我们从第一个数组进行复制，并且我们意识到，从第一个数组进行复制时，至少在拆分反转方面，没有发生真正有趣的事情。
然后，我们将四个复制过来，再一次，我们发现一个分裂的倒数，剩下的是五个逗号四。
再次，原因是，假设之前已复制了四个，则B中剩余的内容将小于它，但是由于位于最右边的数组中，因此它也必须具有更大的索引。
因此，必须进行分割反转。
现在，其余的合并子例程将执行。
没有任何实际事件。
这五个被复制了，我们知道左边数组的复制很无聊。
然后我们复制六个副本，从右数组复制通常很有趣，但如果左数组为空则不是。
这不涉及任何拆分反转。
您会从前面的视频中回忆起，它们是原始数组中的3：2、5：2和5：4。
当我们从正确的数组C复制时，只要注意一下，我们便可以自动发现它们。
因此，这确实是一个一般原则，因此让我陈述一下一般性主张。
因此，声明不仅限于此特定示例和特定执行，而且无论输入数组是什么，无论可能有多少个拆分反转，涉及数组后半部分元素的拆分反转都是恰恰。
将那些元素复制到输出数组时，这些元素保留在第一个数组中。
因此，这正是我们在示例中看到的模式。
在正确的数组上有效的方法。
在C语言中，我们有元素2、4和6。
请记住，按照定义，每个拆分反演都必须包含上半部分中的一个元素，以及下半部分中的一个元素。
因此，要计算[听不清]反转，我们可以根据它们涉及的第二个数组中的哪个元素对其进行分组。
因此，在两个，四个和六个中，两个都涉及拆分器转换3-2和5-2。
这三个和五个正是B中剩余的元素。
超过两个
涉及四个的拆分倒数恰好是五个倒数四个，而五个恰好是我们在四个上进行复制时保留在B中的元素。
没有涉及六个的拆分反转，并且当我们将六个复制到输出数组D中时，元素D实际上是空的。
那么一般的论点是什么？这很简单。
让我们放大并固定在一个特定的元素上，X属于该元素的前一半之中的数组的前半部分，让我们仅检查哪个Y从而使第二个数组的哪个元素位于原始输入数组的后半部分涉及X的拆分版本。
因此，有两种情况取决于X是在Y之前还是之后复制到输出数组D上，如果X很好地复制到Y之前的输出上，则由于[听不清]的排序顺序意味着X必须比Y短因此在反转中不会有任何分裂。
另一方面，如果将y复制到x之前的输出d，则又一次因为我们按排序顺序从左到右填充d，所以这意味着y小于x。
现在是X。
仍在左侧数组中闲逛，因此索引比Y少。
Y来自正确的数组。
因此，这确实是分裂的倒置。
所以把这两个放在一起就说了。
元素X。
数组B。
该形式与Y拆分反演。
到底是那些将要复制到输出数组的对象吗？因此，当y被复制时，这些恰好是b中剩余的元素数。
因此，证明了一般的主张。
[声音]因此，此幻灯片确实是关键见解。
现在，我们确切地知道了为什么，计算拆分反转很容易。
当我们将两个排序的子数组合并在一起时，只需将其转换为代码，并获得子例程的线性时间实现即可，这是一个简单的问题，该例程既合并又计算了拆分反转的数量。
然后，在整个递归算法中，它将具有n log n个运行时间，就像合并排序一样。
因此，让我们花一点时间填写这些细节。
所以。
我不会写出伪代码，我只是写出需要增加合并伪代码的内容，如前几张幻灯片所述，以便在进行合并时计算拆分的倒数。
这将紧接在先前的声明之后，该声明指出了拆分反转与进行合并时保留在左侧数组上的元素数量之间的关系。
所以，这个想法很自然，因为在合并时，根据两个已排序子数组的先前伪代码，您只需保持所遇到的拆分反转总数即可。 ？这样就得到了已排序的子数组b和已排序的子数组c。
您正在将它们合并到输出数组D中。
当您从D到K从1遍历到N时，您只需从0开始计数，然后每次从B或C进行复制时就将其加一。
那么，增量是多少，那么我们刚才看到了什么？我们看到了副本。
涉及B的不算在内。
当我们为B复制时，我们不再关注分割反转。
只有当我们从C看它们时，对吗？每个拆分反演都涉及B和C中的一个元素。
因此，我不妨通过C中的元素来计算它们。
C的给定元素涉及多少个拆分反转？好吧，正是当B被复制时，剩余了B的多少个元素。
这样就告诉我们如何增加此运行计数。
这直接从上一张幻灯片的主张中得出。
该运行总计的实现精确地计数了原始输入数组A拥有的分割反转的数量。
您会记得，左反转由第一个递归调用计算，右反转由第二个递归调用计算。
每个反转都是向左或向右或分裂的，这恰好是这三种类型之一。
因此，使用我们的三个不同子例程，两个递归子例程以及这里的一个子例程，我们成功地计算了原始输入数组的所有求反。
这就是算法的正确性，运行时间是多少？我们所说的合并排序，我们首先分析合并的运行时间，然后讨论整个合并排序的运行时间[听不清]。
让我们在这里简短地做同样的事情。
那么，[音频不清晰]团队的合并时间是多少？
我们在合并中所做的工作，我们已经知道这是线性的，因此这里唯一的附加工作就是。
增加此运行计数。
那是D的每个元素的固定时间，对吗？每次复制完后，我们都会[听不清]，将单个版本记入我们的运行记录中。
因此，元素D的时间恒定，或者总体上是线性时间。
所以我在这里有些草率，以一种非常传统的方式草率。
但是写N的O加N的O等于N的O有点草率。
这样说时要小心，对吗？因此，如果您将N的O加到自身N次，则不会是N的O。
但是，如果您将N的O加到自身恒定的次数，则它仍然是N的O。
因此，作为练习，您可能想要写出这意味着什么的正式版本。
基本上，有一些常数C [听不清]。
合并步骤分步执行C11。
有一个恒定的C2，因此其余工作在这些C2中乘以N步。
因此，当我们将它们相加时，我们得到[听不清]数量最多的C1 + C2乘以N步，这仍然[听不清]，因为C1 + C2是一个常数。
好的？因此，用于合并的线性工作，线性工作的运行次数，即整个子例程中的线性工作。
也不用我们在合并排序中使用的完全相同的参数，因为我们有两个大小为一半的递归调用，并且在递归调用之外进行线性工作，因此总运行时间为N log N的O。
因此，我们实际上只是在合并排序上背负了常量因子来进行计数，但是运行时间仍然是[听不清]。
网友评论