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