すべて、2 つの配列間の反転数を正確に計算する方法を理解しようとしています。
たとえば、次の 2 つの配列があるとします。
A = [1, 2, 3, 4, 5, 6] B = [6, 3, 5, 4, 2, 1]
概念的に反転の数を計算するにはどうすればよいですか? つまり、関連するコーディングを無視して、これら 2 つの配列だけを見ているということです。
また、2 つの配列の間に線分を描画する慣例は知っていますが、ここでより深い理解を得ようとしています。
ありがとうございました！
3216 次
1 に答える
10
2 つの配列の多数の反転が何を意味するのかわかりません。
1 つの配列 の場合: 反転はペア (a,b) であり、a は順序で b より前ですが、a > b です。したがって、概念的には、B の各ペアを試すことができます。6 から始めましょう。(6,3)、(6,5)、(6,4)、(6,2)、(6,1) の 5 つの反転があります。 ）。次の 3 では、(3,2)、(3,1) の 2 つしかありません。など、ここでの結果は 13 です。
ただし、このアルゴリズムは非常に単純で、O(n^2) を実行します。はるかに優れたソリューションは、マージ ソート アルゴリズムに基づいており、O(n log n) で実行されます。ここで確認できます。これは、既にソートされている最初の配列に対してのみ機能すると思います。
2 つの配列の場合: 2 つの配列の場合 (ここでも概念的に)、A 配列の上に B 配列を入力し、同じ要素を結ぶ線を引くだけです。交差の数は、反転の数でなければなりません。これはまさに、上でリンクされたマージソートベースのアルゴリズムがどのように機能するかです。下の写真を見てください。
結果はまだ 13 なので、この方法は実際に機能します。
于 2012-08-06T09:34:20.823 に答える