如问题所述，需要找到数组中满足以下条件的 (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)的时间复杂度。我这样想的原因如下：
第一点：
对于按升序排序一个数组的条件，我们有：对于i第二点：
假设我们有一个元素数组，如下所示：4、9、7、3、2、1、8、12
我们计算上述条件ia[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）时，我们已经计算出小于a[i=0]的3个元素，这些元素又小于a[i=1]，所以我将不会比较9与3、2、1（为了减少不必要的计算）。如果我们可以去除不必要的计算，那么我们就可以将时间复杂度降低到小于O(N^2)，否则不存在小于O(N^2)的解决方案。但如果有解决方案，我们该如何做呢？我试图制作图表，但我的努力是徒劳的。
方法一：
为了获得O(nlogn)的时间复杂度，我认为我们需要调整快速排序或归并排序来获得解决方案，但问题在于，如果我们对数组进行排序，我们将失去元素的实际位置。
方法二：
为了在O(NlogN)的时间内得到解决方案，我认为使用树可能会得到优化的解决方案。我没有得到任何线索。
方法三：
如果存在任何O(N)时间算法，则应使用哈希。但在这种情况下，简单的哈希无法工作。
因此，请告诉我上述哪些直觉或方法是正确的（如果正确，哪种方法将导致优化的解决方案以及如何）。