计算反演次数(从概念上讲？)

Question

所有,我试图了解我们究竟是如何计算两个数组之间的反转次数.

比方说,我们有以下两个数组:

A = [1,2,3,4,5,6] B = [6,3,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)中运行.你可以在这里查看.我认为这仅适用于已排序的第一个数组.

对于两个数组:当涉及2个数组(再次在概念上)时,只需在A数组上方键入B数组并绘制连接相同元素的线.交叉的数量应该是反转的数量.这正是上面链接的基于合并排序的算法的工作原理.看看下面的图片:

结果仍然是13,所以这种方法确实有效.