整数の配列 a を考えてみましょう。i < j かつ A[i] > A[j] の場合、ペア (i,j) は A の反転と呼ばれます。
配列内のすべての位置 'i' に対して、確率 p[i] の a[i] と確率 1-p[i] の a[i]+x の 2 つの候補があります。
次に、予想される反転数を計算する必要があります。すべてのインデックス i と整数 x に対して a[i] と p[i] が与えられます。
私は O(n^2) アプローチを知っています (すべての有効なペアをチェックしてください)。また、すべての要素が 100% の確率で事前に決定されている配列の反転数を計算する O(nlogn) アプローチを知っています。これは、マージソートを変更することによって行われます。
n二乗よりも優れたアプローチを知りたいです。私にお知らせください。
これは、反転をカウントするための標準のマージソートベースのアルゴリズムを簡単に変更することで実行できます。このアルゴリズムでは、各値に重みを割り当て、W[i]*W[j]fori<jの合計を計算しますA[i]>A[j](各重みが 1 の場合、通常のカウントを取得します)。左側の配列に残っている要素の数をカウントに追加する代わりに、これらの要素の重みの合計に、処理中の右側の配列の要素の重みを掛けたものを追加します。
このアルゴリズムを使用して提起された問題を解決するには、単純に 2 倍のサイズの配列を作成します。この配列では、元の配列の各要素が (並べ替えられた順序で) 2 つの要素に置き換えられ、重みは確率で与えられます。
これを説明するコメントを残しましたが、少し数学を使用するだけで、これを O(1) 計算することができます。作業は割愛しますが、私の計算では、n 個の整数の配列で予想される反転の数は ((n^2) - (n)) / 4 です。括弧が多すぎて申し訳ありません。それが完全に明確であることを確認するために。必要に応じて作品を投稿できますが、答えだけが必要な場合は省略します.
だから、私のコメントが言っているにもかかわらず、私は間違って覚えていました。lg(n) ではありません。