行列式中逆序数怎么算_逆序数在行列式的意义

大家好，我是讯享网，大家多多关注。

原创不易，求关注。

我们之前在介绍线性代数行列式的公式时，曾经介绍过逆数:在列出行列式的每一项后，需要通过逆数来确定该项的符号。如果你已经忘记了，你可以回到上一篇文章回顾一下:

线性代数的本质1-从行列式开始

如果忘了，问题不大。这个概念比较简单，我想大家很快就能想明白。

在今天的文章中，我想和大家谈谈倒数的算法，这也是一个非常经典的算法问题，经常出现在各大公司的面试题中。

我们先来回顾一下逆数的定义。所谓倒数，是指一个数组中存在多少对数，使得前面的数大于后面的数。我们举个例子，假设此刻有一个数组:[1，3，2]。

对于数对(3，2)，由于3在2之前，且3 >: 2，则(3，2)是一对逆序的数。整个数组中所有逆数对的个数就是逆数。

从逆序数的定义中不难发现，逆序数其实是一个用来衡量数组有序程度的指标。倒数越大，这个数组的增量越差。如果逆序数为0，则此序列严格递增。如果一个长度为n的数组的逆序数是C_n2，说明这个数组是严格递减的，逆序数最大。

那么，我们如何快速求解倒数呢？

暴力解法

显然这个问题是可以暴力解决的。我们只需要遍历所有的数对，然后判断它们是否构成逆序。最后，把所有数字对的数字按逆序相加就是最终答案。

这段代码非常简单，它只需要几行代码:

当然这是可能的，但是我们很容易发现这其中的时间复杂度是O (n 2)，这往往是我们无法接受的。即使是运行速度非常快的C++，在单核CPU上一秒钟也能运行到n=1000的规模。需要的时间会突然增加，在实际应用中，长度超过1000的数组是常有的事。显然，我们需要优化这个算法，不能简单地暴力解决。

分治

我们可以尝试用分治算法来解决这个问题。

对于数组arr，我们试图把它分成两半。例如，当前arr是[32，36，3，9，29，16，35，73，34，82]。我们分成两半后，分别是[32，36，3，9，29]和[16，35，73，34，82]。设左半部分的子阵列为A，右半部分的子阵列为B，显然A和B都是原问题的子问题。我们可以假设A和B子问题的结果可以通过递归来解决。

那么问题来了。如何通过子问题A和B的结果来构造arr的结果？也就是说，如何通过分分题得到原问题的答案？

在回答之前，我们先分析一下目前的情况。当我们把arr数组拆分成两部分AB时，整个arr的逆序就变成了三部分。分别是数组A内部的逆序号，数组B内部的逆序号，两个数组AB之间的逆序号，即A中一个元素和B中一个元素的逆序号对。

我们再分析一下，会发现数组A中元素的交换位置只会影响数组A之间的逆序数，而不会影响B和AB之间的逆序数。因为A中的元素在数组B中的所有元素之前，即使它们改变了位置。

让我们举个例子:

假设arr=[3，5，1，4]，那么A=[3，5]，B=[1，4]。

对于arr，它的逆序数是3，即(3，1)、(5，1)和(5，4)。对于A，它的逆序数是0，B的逆序数也是0。我们试着在B之间互换位置，之后B = (4，1)，此时arr=[3，5，4，1]。那么B的逆序号就变成了1，A的逆序号还是0。而整体arr的逆序数变成了4，分别是:(3，1)、(5，1)、(5，4)、(4，1)。很明显，整体ARR的新逆序号是B交换元素带来的。

通过观察我们还可以发现，对于A中的3和5，B中的1和4的顺序并不影响它们的倒数的个数。

知道了这一层，剩下的就简单了。由于A和B中的元素无论如何交换都不会影响彼此的结果，所以我们可以放心地使用分治算法来求解。我们先假设可以通过递归得到A和B的逆序数。那么剩下的问题就是合并AB后的倒数对，也就是找出所有A和B各占一个元素的倒数对。

我们先对A和B中的元素进行排序。我们以前验证过。如果我们调整A或B中元素的顺序，不会改变跨AB的倒装数的个数。我们已经通过递归得到了A和B中的倒数对的个数，那么我们保存后就可以对A和B中的元素进行排序，A和B中的元素排序后，通过插入和排序就可以将A中的元素依次插入B中。

从上图可以看出，假设我们将元素A[i]插入到数组B中J的位置，由于A[i]在J个元素B之前，所以构成了J对逆序的数。对于A中的所有元素A[i]，我们可以找出它们在数组B中的位置J，然后对J求和。

很容易认为，因为B的元素是有序的，所以可以通过对分找到A中元素的位置。但其实还有更好的办法。我们可以一步完成AB的排序和插入，即合并AB的两个有序数组。在归并的过程中，不仅可以知道插入的B数组的位置，还可以完成数组的排序，从而顺便解决了数组排序的问题。所以整个步骤实际上是合并排序的扩展。虽然全代码和归并排序的区别很小，但是这个过程中的推演和思考很重要。

如果你能理解上面的推导过程，相信代码对你来说并不难。如果你还没有完全理解，没关系。有了代码的帮助，相信你会更容易理解。事不宜迟，让我们看看代码:

从代码层面来说，上面的代码实现了排序，也计算了逆序数。所以这也是很多人比较两者的原因，也是我个人非常喜欢这个问题的原因。两个看似毫不相关的问题，几乎可以用同一套代码解决，不得不感叹算法的神奇。正是因为这个原因，我们这些算法的研究者和学习者才能获得源源不断的乐趣。

今天的文章到此为止。如果你觉得你有所收获，请关注一下。你的支持是我最大的动力。