考虑一个整数数组 a。如果 i < j 且 A[i] > A[j]，则对 (i,j) 称为 A 中的反转。
对于数组中的每个位置“i”，都有两个可能的候选者：a[i] 概率为 p[i] 和 a[i]+x 概率为 1-p[i]。
现在我必须计算预期的反转次数。给定每个索引 i 的 a[i] 和 p[i] 以及一个整数 x。
我知道 O(n^2) 方法（检查每个合法的可能对）。另外，我知道 O(nlogn) 方法来计算数组中的反转次数，其中所有元素都以 100% 的概率预先确定。它是通过修改归并排序来完成的。
我想知道一种比 n 平方更好的方法。请告诉我。
这可以通过对基于标准合并排序的倒数计数算法进行简单修改来完成，我们为每个值分配一个权重并计算W[i]*W[j]fori<j的总和A[i]>A[j]（当每个权重为 1 时，我们得到正常计数）。我们不是将左侧数组中剩余的元素数量添加到计数中，而是将这些元素的权重之和乘以我们正在处理的右侧数组中元素的权重。
要使用此算法解决提出的问题，只需创建一个大小为两倍的数组，其中原始数组中的每个元素都被两个元素替换（按排序顺序），权重由概率给出。
我留下了一条评论来解释这一点，但如果你只使用一点数学，你可以对此进行 O(1) 计算。我会省去你的工作，但是，根据我的计算，在 n 个整数的数组中，预期的反转次数是 ((n^2) - (n)) / 4。抱歉，括号太多了，我只是想要以确保完全清楚。如果你想要，我可以发布作品，但我想如果你只需要答案，我会忽略它。
所以，尽管我的评论说了什么，我还是记错了。这不是 lg(n)。