ようアレイにおいて（i、j）の対の合計数を見つけるよう私<j and a[i]> [J]配列で（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）時間がかかるブルートフォアを使用している質問を行う
一つの方法を以下のように
私のアプローチがあります。
しかし、私は私の第二の直感がある
直観 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 .
を次のように私の勘のためのO（NlogN）sollution【選択理由がある時に、少なくともこの質問へのより良い最適化された解決策があるはずだと思います：4,9,7,3,2,1,8,12
を我々はiと、要素4の条件i<j , a[i]>a[j]上記で計算：
は、次のように我々は、素子のアレイがあると= 0は4を指し、jの可能な値は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）のとき、[i = 0]より小さい3つの要素を計算しました。これはa [i = 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 .
だから、私は正しいどのアプローチが最適化されたsollutionにつながる場合には（正しい上記の直感やアプローチのどの教えてくださいそしてどうやって）。
「* O未満（N^2）*」を意味しますか？私は技術的にO（N * 2）はO（N）と同じものであり、「O（N2）」の意味を明確にしていないからです。 – RBarryYoung
はい私はO（N^2）を意味します – Imposter
あなたはそのようなペアのカウントを見つけようとしているのですか、それらを列挙しようとしていますか？ –