サイトで反転が意味することを読んだことがありますが、i<j
これA[i]>A[j]
についていくつかの演習があります。多くの質問がありますが、最初はそのうちの1つだけを尋ねてから、できれば自分で他の演習を行います!!
演習:どの順列配列 (1,2, ..., n) が最大の反転数を持っていますか? これは何? ありがとう
サイトで反転が意味することを読んだことがありますが、i<j
これA[i]>A[j]
についていくつかの演習があります。多くの質問がありますが、最初はそのうちの1つだけを尋ねてから、できれば自分で他の演習を行います!!
演習:どの順列配列 (1,2, ..., n) が最大の反転数を持っていますか? これは何? ありがとう
明らかN, ..., 2, 1
に反転の数が最も多くなっています。すべてのペアは反転です。たとえばN = 6
、 があり6 5 4 3 2 1
ます。反転など6-5, 6-4, 6-3, 6-2, 6-1, 5-4, 5-3
です。その数はN * (N - 1) / 2
です。
恒等順列 (1,2,...,n) には反転がありません。反転はインデックスとは逆の順序になっている要素のペアであるため、答えにはおそらくその順列の反転が含まれます。
このように使用される反転という用語は聞いたことがありません。
長さ N の減少する配列 (N>0 の場合) には、1/2*N*(N-1) ペア i<j と A[i]>A[j] があります。これが最大の可能性です。