如何用 O(n) 的时间复杂度求数组的逆序对数 ?

以前听某个神牛说有 O(n) 算法的,但是好像没有流传的资料。。

我的回答

先说结论:基于比较操作的统计逆序对算法最坏时间复杂度下界是 $\Omega(n\log{n})$ 。

解决这个问题最核心的一点是理解一次 “比较” 操作的本质是什么,我先放一张大图

为了讨论方便起见,我们不妨假设数组 $a_1$ , $a_2$ , $a_3$ , $…$ , $a_n$ 中没有重复元素,那么它们的相对大小关系一共就有 $n!$ 种可能排列。而对于一次 “比较” 操作,本质上就是把当前的的可能排列划分成了两部分。因此想要确定最终排列,就必须反复 “比较” 来划分可能排列,选择相应的分支继续直至可能排列只有一种。这是算法导论上的内容,它由此证明了基于比较操作的排序算法最坏时间复杂度下界是 $\Omega(n\log{n})$ 。

对于排序来说这是很直观的,因为它的解空间大小就是 $n!$ 。但统计逆序对却没有那么显然,因为它的解空间大小是 $n(n-1)/2 + 1$ ,我们很有理由质疑说万一我不需要将可能排列划分到只有一种呢?也就是说有没有可能划分解空间到某一步以后,当前的所有可能排列(大于一种)都对应着相同的逆序对数,那样我们也就可以不用继续划分而直接返回这个统一值就好了?

很遗憾这是不可能的,参考我放的大图。“比较” 操作其实对应了对可能排列(解空间)的划分,而这个在图上看就是从根节点一层一层往下走。椭圆形节点代表了当前的可能排列还能继续划分,长方形节点代表了已经确定好了最终排列。这里值得注意的是绿色的椭圆形节点,如果我们把所有椭圆形节点看作一棵树的话,那么白色的椭圆形节点是内部节点,而绿色的椭圆形节点则是叶子节点。

那么对于每个叶子节点,一个很明显的特征就是它包含了两个可能排列,并且可以通过一次比较来划分它们。更重要的是,这两个可能排列的逆序对数相差了一个,它们不可能拥有相同的逆序对数。因此不管你停留在哪一个椭圆节点,都不可避免地包含至少一个叶子节点,也就不可避免地包含两个逆序对数不相等的可能排列,你就得继续往下划分。最终也就证明了想要基于比较操作来统计逆序对,最坏时间复杂度下界和排序一样,也是 $\Omega(n\log{n})$ 。

最后补充说一点,通常见到的统计逆序对算法(譬如扩展归并排序、扩展二叉搜索树或者树状数组)不单单能统计一个总的逆序对数,还能分别统计以每个元素开头的逆序对数,这是一个更强的结果,因为知道了后者,就必定能在线性时间复杂度内将原数组排序。

至于 $O(n)$ 复杂度的传言,我大致去搜索了一下应该是这样的:

  • 1989年,Dietz 在论文 《Optimal Algorithms for List Indexing and Subset Rank》里面给出了均摊复杂度是 $O(\log{n}/\log\log{n})$ 的单点更新区间求和算法,因此理论上可以把统计逆序对算法的复杂度优化到 $O(n\log{n}/\log\log{n})$ ,可惜他的算法是对更新数字和机器字长有特殊要求的;
  • 1995年,Andersson 和 Petersson 在论文《Approximate indexed lists》里面提出了 $O(n\log{\log{n}})$ 的近似算法,注意,是近似算法;
  • 2010年,Chan 和 Pătraşcu 在论文《Counting Inversions, Offline Orthogonal Range Counting, and Related Problems》里面给出了时间复杂度为 $O(n\sqrt{\log{n}})$ 的算法,同时还给出了时间复杂度为 $O(n)$ 的近似算法,不过同样,他们都不是只基于比较操作的。