计算反演次数（概念上？）

Question

所有的，我想知道我们究竟是如何计算两个数组之间的反转次数的。

比方说，例如，我们有以下两个数组：

A = [1，2，3，4，5，6] B = [6,3,1，5,4，2， 1]

我如何计算概念上的反演次数？也就是说，只要看看这两个阵列，不考虑涉及的编码。另外，我知道两个数组之间绘制线段的约定，但我试图在这里获得更深入的理解。

谢谢！

Answer 1

我不确定两个数组的反转数是什么意思。

对于一个阵列： 反演是一对（a，b），其中a在b之前的顺序为a> b。因此，从概念上讲，你可以尝试每一对B。让我们从6开始，有5个反转：（6,3），（6,5），（6,4），（6,2），（6， 1）。接下来是3，只有2：（3,2），（3,1）。等等，这里的结果是13.

但是，这个算法是非常天真的，运行O（n^2）。更好的解决方案是基于合并排序算法，并以O（n log n）运行。你可以检查它here。我认为这只适用于已经排序的第一个数组。

对于两个阵列：当涉及到2门阵列（再次在概念上），只要输入你的乙阵列上方A排列并绘制连接相同的元件线。交叉点的数量应该是反转次数。这正是上面链接的基于合并分类的算法的工作原理。看看下面的图片：

的结果仍是13，所以这种方法确实有效。