整型数组的最佳反转计数

Question

今天我看到了当地信息学奥林匹克竞赛的最新考试，发现了一个有趣的问题。简单来说，它要求给定一个整数数组，计算它有多少个逆序对，其中逆序对是一对索引 i 和 j ，使得 i > j并且。通俗地说，逆序对的数量是无序对的数量。最初，我想到了一个O（n²）的解决方案（是的，是朴素的），但是看到它不适合输入的大小，我更加深入地思考了这个问题，然后我意识到可以通过归并排序的变体在 O（n log n）的时间内处理好输入的大小。

但是看到输入约束（ n 介于 1和M 之间的整数，并且没有重复项），我想知道我的解决方案是否最优，或者您是否知道是否还有其他解决方案可以击败 O（n log n）的运行时间？

- Luiz Rodrigo

---

什么是反转？我在与数组相关的其他地方看到了这个术语，但无法完全理解其含义。 - Will A

好的 - 我找到了自己问题的答案 - 对于数组A，如果A[i] > A[i + j]，其中j > 0，则A[i]和A[j]是一种逆序。这只是两个元素相对于彼此“自然顺序”不同的一个花哨术语。 - Will A

哦，抱歉，也许我应该解释一下。 - Luiz Rodrigo

在计算机世界中，除了O(n)之外，什么比O(n log n)更好呢？ - Will A

n和M有什么限制？可以使用类似于计数排序的算法在O(n * M)的时间复杂度内完成，但这很难超过O(n log n)的算法。 - IVlad

Answer 1

文献中最好的结果是由Chan and Patrascu提出的O(n √(log n))算法。关于常数没有任何想法。

- slowpoke

---

有趣的是，我一直认为逆序问题与排序具有相同的下限，因此在这种情况下，有许多线性算法可用于排序，同样也可以用于逆序问题。无论如何，谢谢你的答复！ - Luiz Rodrigo

Answer 2

据我所知，O(n log n)是最好的。

这里有详细的解释：

http://www.geeksforgeeks.org/counting-inversions/

- banarun

Answer 3

如果我们假设用于表示整数的位数是恒定的（比如32或64位），那么这个问题可以在O(N)时间内解决。

以下是一个Python实现示例。

http://ideone.com/g57O87

def inv_count(a, m=(1<<32)):
  if not m or not a:
      return 0
  count = 0
  ones = []
  zeros = []
  for n in a:
    if n & m:
      ones.append(n & ~m)
    else:
      count += len(ones)
      zeros.append(n & ~m)
  m /= 2
  return count + inv_count(ones, m) + inv_count(zeros, m)

print inv_count([1, 2, 3, 4, 5]) print inv_count([5, 4, 3, 2, 1])

我们能够实现小于O（N x Log（N））的时间复杂度，因为我们使用了非比较排序算法radix sort的思想来获取计数。

- therealsachin