algorithm - 计算反转次数

Question

设A[1...n]是一个由 n 个不同数字组成的数组。

该对(i, j)被称为逆，如果i < j and A [i] > A [j]。

例子：

A := (2, 3, 8, 6, 1) => A 有 5 个逆。

任务：

编写程序找出数组 A [1..n] 的逆数，使得算法的复杂度为 O (n * logn)。

Answer 1

这个问题可以基于归并排序来解决。

严格来说，您应该修改merge(A, B)它返回对数的过程(a, b) such that a in A, b in B and b > c。

如您所见，解决此问题所需的运行时间是归并排序的运行时间，因此O(n * log(n))