2

配列 A[1:N] は、1<= k<= N の場合 |k-rank(A[k])|<=d の場合、d-unsorted であると言われます。

そして、ソートされていない配列 A[1:N] の反転の数

は、1<=j< k<= N および A[k]< A[j] となるペア (j,k) の数です。

例えば。[2,4,1,5,3] には 4 つの反転があり、2-unsorted です

私の質問は、配列内の反転の最大数を d に関連付けることができますか?

配列の d-unsorted の量を知っている配列の反転の最大数を見つける式を取得できますか?

4

0 に答える 0