如问题中所述，需要在数组中找到 (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(index) 增加到 1 时， j 的可能值为 2,3,4,5,6 。但是我们应该使用这样一个事实，即当 i=0 时（当 a[i]=4 时）我们计算了比 a[i=0] 少 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 .
所以请让我知道上述哪些直觉或方法是正确的（如果正确，哪种方法将导致优化的解决方案以及如何）。