algorithm - 反転数を計算する

Question

をnA[1...n]個の異なる数からなる配列とします。

このペア(i, j)は、逆の Ifと呼ばれi < j and A [i] > A [j]ます。

例：

A := (2, 3, 8, 6, 1) => A には 5 つの逆数があります。

仕事：

アルゴリズムの複雑さが O (n * logn) になるように、配列 A [1..n] の逆数を求めるプログラムを作成します。

Answer 1

この問題は、マージソートに基づいて解決できます。

厳密に言えば、merge(A, B)ペアの数を返すようにプロシージャを変更する必要があります(a, b) such that a in A, b in B and b > c。

ご覧のとおり、この問題を解決するために必要な実行時間は、マージ ソートの実行時間です。O(n * log(n))