So the answer to this question is the first one.
Fifteen.
Or in general in an N.
Element array the largest number of inversions is N.
Choose two.
Also known as N times N minus one over two.
Which, again, in the case of a [inaudible] is going to evaluate to fifteen.
The reason is, the worst case is when the array is in backwards order, reverse [inaudible] order, and every single pair of [inaudible] indices is inverted.
And so the number of indices IJ, with I less than J is precisely [inaudible] too.
Let's now turn our attention to the problem of computing the number of inversions of an array as quickly as possible.
So one option that is certainly available to us is the brute force algorithm.
And by brute force I just mean we could set up a double four loop.
One which goes through I, one which goes through J bigger than I, and we just check each pair IJ individually with I less than J whether that particular pair of array entities AI and AJ is inverted and if it is then we add it to our running count.
And then we return the final count at the end of the double four loop.
That's certainly correct.
The only problem is, as we just observed, there's N [inaudible] two or a quadratic number of potential inversions so this algorithm's almost going to run in time quadratic in the array link.
Now remember the mantra of any good algorithm designer.
Can we do better? And the answer is yes.
And the method we'll be using, divide and conquer.
The way in which we'll divide will be motivated directly by merge sort where we recurs e separately on the left and the right half's of the array.
We're gonna do the same thing here.
To understand how much progress we can make purely using recursion let's classify the inversions of array into one of three types.
So suppose we have an inversion of an array I, J, and remember in an inversion you always have I less than J.
We're gonna call it a left inversion.
If both of the array indices are at most N over two, where N is the array length.
We're gonna call it a right inversion if they're both strictly greater than N over two.
And we're gonna call it a split inversion if the smaller index is at most N over two and the larger index is bigger than N over two.
We can discuss the progress made by recursion in these terms.
When we recurse on the left-half of an array, if we implement our algorithm correctly, we'll successfully be able to count all of the inversions located purely in that first half.
Those are precisely the left inversions.
Similarly, a second recursive call on just the right half of an array, the second half of an [inaudible] array will successfully count all of the right inversions.
There remains the questions of how to count the split inversions.
But we shouldn't be surprised there's some residual work left over, even after the recursive calls do their job.
That, of course, was the case at Merge Short, where [inaudible] magically took care of sorting the left half of the array, sorting the right half of the array.
But there was still, after their return, the matter of merging those two sorted lists into one.
And here again, after the recursion is gonna be the matter of cleaning up and counting the number of split inversions.
So for example if you go back to the six element array we worked through before, 135246, you'll notice that there, in fact, all of the inversions are split.
So the recursive calls will both come back counting zero inversions.
And all of the work for that example will be done by the count split inversions subroutine.
So let's summarize where things stand given underspecified high level description of the algorithm as we envision it.
There is a base case.
I'll go ahead and write it down for completeness, which is if we're given a one element array, then there's certainly no inversion so we can just immediately return the answer zero.
For any bigger array, we're going to divde and conquer.
So we'll count the left inversions with a recursive call.
The right inversions with a recursive call.
And then we'll have some currently unimplemented subroutine that counts the split inversions.
Since every inversion is either left or right, or split, and can't be any more than one of those three, then, having done these three things, we can simply return their sum.
So that's our high level attack on how we're gonna count up the number of inversions.
And of course, we need to specify how we're gonna count the number of split inversions.
And moreover, we lack that subroutine to run quickly.
An analogy to emerge short, where, outside the recursive calls, we did merely linear work.
Outs-, in the merge subroutine.
Here, we'd like to do only linear work in counting up the number of split inversions.
If we succeed in this goal, if we produce a correct and linear time of limitation to count up the number of split incursions, then this entire recursive algorithm will run in big O.
Of N.
Log in time.
The reason the overall out rhythm will run in O.
Of N.
Log in time is exactly the same reason that merge short ran in N.
Log in time.
There's two recursive calls.
Each on a problem of one-half the size.
And outside of the recursive calls we would be doing linear work.
So you could copy down exactly the same recursion tree argument we used for merge short.
It would apply equally well here.
Alternatively, very soon we will cover the master method, and as one very special case it will prove that this algorithm, if we can implement it thusly, will run in O.
Of N.
Log in time.
Now one thing to realize, is this is a fairly ambitious goal, to count up the number of split inversions in linear time.
It's not that there can't be too many split inversions.
There can actually be a lot of them.
If you have an array where the first half of the array contains the numbers N over two plus one, up to N.
Whereas the second part of the array contains the numbers one up to N over two, that has a quadratic number of inversions, all of which are split.
So, what we're attempting to do here is count up a quadratic number of things using only linear time.
Can it really be done? Yes is can, as we'll see in the next video.
因此，这个问题的答案是第一个。
十五。
或一般在N。
元素数组的最大反转数为N。
选择两个。
也称为N乘N减二乘一。
同样，在[听不清]的情况下，结果将为15。
原因是，最坏的情况是当数组按向后顺序，[听不清]反向，并且每对[听不清]索引都被反转时。
因此，索引IJ（I小于J）的数量也正是[听不清]。
现在，让我们将注意力转向尽快计算数组的求逆数的问题。
因此，我们当然可以使用的一种选择是蛮力算法。
通过蛮力，我只是说我们可以建立一个双四环。
穿过I的一个，穿过J的一个大于I的，我们只是单独检查每对IJ，而我的I小于J，则这对特定的数组实体AI和AJ是否反转了，如果是，则将其添加到我们的数组中运行计数。
然后，我们在双四循环的末尾返回最终计数。
这是正确的。
就像我们刚刚观察到的那样，唯一的问题是，存在N个[听不清]两个或二次数的潜在求逆，因此该算法几乎将在数组链接中以二次时间运行。
现在，请记住任何优秀算法设计师的口头禅。
我们可以做得更好吗？答案是肯定的。
我们将使用的方法是划分和征服。
划分方式将直接由合并排序驱动，合并排序是在数组的左半部分和右半部分分别递归e。
我们将在这里做同样的事情。
要了解仅使用递归就可以取得多少进展，让我们将数组的倒置分类为三种类型之一。
因此，假设我们有一个数组I，J的求逆，并且记住在求逆中，我的I总是小于J。
我们将其称为左反转。
如果两个数组索引的最大值都大于2，则N是数组长度。
如果它们都严格大于N大于2，我们将其称为右反转。
如果较小的索引最多是N大于2，而较大的索引大于N超过2，则我们将其称为拆分反转。
我们可以用这些术语讨论递归所取得的进展。
当我们对数组的左半部分进行递归时，如果我们正确地实现了我们的算法，那么我们将能够成功地计算出纯粹位于前半部分的所有反转。
这些恰恰是左反转。
同样，在数组的右半部分（[听不清]数组的后半部分）进行第二次递归调用将成功计算所有正确的反转。
仍然存在如何计算分裂倒数的问题。
但是，即使递归调用完成了工作，我们也不会感到惊讶。
当然，Merge Short就是这种情况，其中[听不清]神奇地负责对数组的左半部分进行排序，对数组的右半部分进行排序。
但是，在他们返回之后，仍然存在将这两个排序列表合并为一个的问题。
再一次，在递归之后将是清理并计算分割反转的次数。
因此，例如，如果您回到我们之前研究过的六元素数组135246，您会发现实际上所有的反转都是分裂的。
因此，递归调用都将返回零计数。
该示例的所有工作将由count split inversions子例程完成。
因此，让我们在预想不到的情况下，对该算法的未得到充分说明的高级描述进行总结。
有一个基本案例。
为了完整起见，我将其写下来，即如果给我们一个单元素数组，那么肯定没有反转，因此我们可以立即将答案返回零。
对于更大的数组，我们将进行分而治之。
因此，我们将通过递归调用计算左反转。
通过递归调用进行正确的反转。
然后，我们将使用一些当前未实现的子例程来计算拆分的倒数。
由于每个反转都是向左或向右或分裂，并且最多只能是这三个反转之一，因此，完成这三件事之后，我们可以简单地返回它们的总和。
这就是我们对如何计算反转次数的高级攻击。
当然，我们需要指定如何计算分割反转的数量。
而且，我们缺少该子例程来快速运行。
打个比方说，在递归调用之外，我们只做线性工作。
Outs-，在合并子例程中。
在这里，我们只想做线性工作来计算分割反演的次数。
如果我们成功实现了这一目标，并且我们产生了正确的线性限制时间来计算拆分入侵的数量，那么整个递归算法将以大O运行。
N的
登录时间。
整体节奏在O中运行的原因。
N的
登录时间与合并短时间在N中运行的原因完全相同。
登录时间。
有两个递归调用。
每个问题只有一半的大小。
在递归调用之外，我们将进行线性工作。
因此，您可以复制与用于合并short相同的递归树参数。
在这里同样适用。
或者，很快我们将介绍master方法，并且作为一种非常特殊的情况，它将证明该算法（如果我们可以实现的话）将在O中运行。
N的
登录时间。
现在要实现的一件事是，这是一个相当雄心勃勃的目标，它可以计算线性时间中分割反转的数量。
并不是说分裂反转不会太多。
实际上可能有很多。
如果您有一个数组，其中数组的前半部分包含2加上1的数字N，则最多为N。
而数组的第二部分包含一个数字，最多一个大于N的两个数字，该数字具有一个二次数的求逆，所有求逆均被拆分。
因此，我们在这里尝试做的是仅使用线性时间来计算二次数。
真的可以做到吗？是的，可以的，我们将在下一个视频中看到。
