質問で述べたように、配列内の (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 ?
質問が明確であることを願っています。
私のアプローチは次のとおりです
質問を行う 1 つの方法は、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 .
私の2番目の直感は次のとおりです。
次のような要素の配列があるとします: 4,9,7,3,2,1,8,12
i<j , a[i]>a[j] i=0 が 4 を指しているため、上記の要素 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=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 .
したがって、上記の直感またはアプローチのどれが正しいか教えてください（正しい場合、どのアプローチが最適化されたソリューションにどのようにつながるか）。