找到数组中的(i,j)对的总数,使得i <j和a [i]> a [j]

Question

如问题所述,需要在数组中找到(i,j)对的总数

(1) **i<j** 
(2) **a[i]>a[j]**

其中i和j是数组的索引.没有空间限制.

我的问题是

 1) Is there any approach which takes less than O(N^2) time?
 2) if so what is least complexity ?
 3) How do we prove that ? 

我希望我对这个问题很清楚.

我的方法如下

解决这个问题的一种方法是使用粗暴的前置,这需要花费O(N ^ 2)的时间.

但我认为应该有一个更好的优化解决方案,至少O(NlogN)溶解这个问题.我直觉的原因如下

直觉 1) For sorting an array in ascending order conditions we have are : for i<j , a[i]<a[j] which is similar to my question . I also read that sorting has lower bound of Omega(n log n) . So my question should also have Omega(n log n) . I may be completely wrong if so please correct me .

我的第二个直觉是:

假设我们有一系列元素如下:4,9,7,3,2,1,8,12

我们计算i<j , a[i]>a[j] 元素4的上述条件,因为i = 0指向4,j的可能值是3,4,5.因为a [0]> a [3],a [0]> a [4],a [0]> a [5],所以我现在的(i,j)对的总数是3.下次当我将i(索引)增加到1时,j的可能值为2,3,4,5,6.但是我们应该使用这样的事实:当i = 0时(当a [i] = 4时)我们计算出3个小于a [i = 0]的元素,而这个元素又小于a [i = 1],所以我不会比较9和3,2,1(去除不必要的计算).如果我们可以删除不必要的计算,那么我们可以将复杂度降低到小于O(N ^ 2)的值,否则不存在小于O(N ^ 2)的解.但如果存在解决方案,那么我们如何做到这一点.我尝试制作图表,但我的努力是徒劳的.

方法1)In-order to obtain O(nlogn) complexity I think we need to tweak around quick sort or merge sort to get solution but problem here is, if we sort the array we loose the actual positions of elements.

途径 2)In-order to get solution in O(NlogN) time I think using tree we may get the optimised sollution . I didn't get any clue.

方法3)If there exists any O(N) time algorithm it should be with hashing . But in this case simple hashing doest work .

所以,请让我知道上述哪些直觉或方法是正确的(如果正确哪种方法将导致优化的溶出度以及如何).

Answer 1

你可以指望的算法倒对,类似于归并排序,如解释在这里.

我的想法是在计算时合并排序数组,每一步改变了多少次反转.

另一种方法是使用订单统计树.您按顺序将数组的元素插入到此树中,并在每次插入后看到插入元素之前的元素数量大于它.

订单统计树的替代方法是Indexable skiplist.

两种算法都具有O(N log N)时间复杂度.

为了获得近似的反演次数,O(N)时间复杂度可能存在一些限制.我们可以像修改合并排序一样修改Bucket排序.

在Bucket排序的"分散"阶段,我们应该估计较大元素的桶中元素的数量,而在某个桶的末尾插入元素(每个桶中的元素保持原始顺序).

在Bucket排序的"排序"阶段,我们应该修改(以相同的方式)排序算法(插入排序,最有可能).在将元素插入适当的位置时,我们应该计算它跳过的其他元素数量.

至于限制,此算法仅适用于数字(或使用对象,可轻松转换为数字),我们应事先知道这些数字是如何分布的.因此,如果我们有一个均匀分布的整数数组,这个算法应该可以正常工作.

Answer 2

这样的对称为数组中的反转次数。它是衡量数组与排序的接近程度的一种度量。您可以修改合并排序以有效地计算 O(nlogn) 时间内的反转次数。请参阅此了解详情。