4

さて、私はここで複雑さにとらわれ続けています。要素の配列があります、例えばA[n]。すべてのペアを見つける必要があるのでA[i]>A[j]、またi < j。

したがって、の場合{10, 8, 6, 7, 11}、ペアは次のようになります。(10,8) (10, 6), (10,7) and so on...

nlogn時間でマージソートを実行してから、nlognで配列全体を再度バイナリ検索して、ソートされた配列内の要素のインデックスを取得しました。

だからsortedArray={6 7 8 10 11}そしてindex={3 2 0 1 4}

私が何をしようとしても、n^2比較するためにループを開始するとき、私は複雑さの中で別の時間を取得し続けます。つまり、最初の要素、つまり10から始めると、それはindex[2]それより2つ少ない要素があることを意味します。したがって、その場合index[2]<index[i]は受け入れることができますが、それによって複雑さが増します。何かご意見は？コードは必要ありません。正しい方向へのヒントが役立つでしょう。

ありがとう。私がCで行ってきたすべてのことと、時間計算量はここで重要です

4

2 に答える 2

4

O(N^2)元の配列が降順でソートされたときにアルゴリズムが生成するペアの数がであるため、これを下で行うことはできませんN(N-1)/2。O(N^2)時間内に結果を出すことはできませんO(N*LogN)。

于 2012-08-29T11:12:01.723 に答える
2

結果はO（n ^ 2）要素で構成されるため、すべてのペアを反復処理しようとするとO（n ^ 2）になります。

于 2012-08-29T11:13:50.007 に答える