如何计算半随机整数数组中“期望”的逆序对数量？

Question

考虑一个整数数组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％预定概率的数组中逆序对的数量。它通过修改归并排序来完成。

请告诉我一种比O(n^2)更好的方法。

- Abhinav Chauhan

---

我只知道当数组的所有元素已经以100％的概率知道时，nlogn是可行的解决方案，但在这种情况下，每个位置都有两个候选项，因此无法使用该方法。 - Abhinav Chauhan

哦，针对这个问题，你确定有一个O(n**2)的解决方案吗？我认为有2 ** length(a)种不同的组合。如果你有这样的方法，能否解释一下是什么呢？ - argentage

有C(n,2) = O(n^2)个可能的配对。其中，我只需要检查那些i < j的配对(i,j)。检查每个配对需要O(1)的时间。 - Abhinav Chauhan

我不需要创建数组的每个可能实例。对于任何一对(i,j)，我只需要确定逆序的概率即可。通过知道ai、pi和x，我可以在O(1)时间内完成这个过程。 - Abhinav Chauhan

不，它并不总是lg(n)。答案取决于输入。 - Abhinav Chauhan

Answer 1

这可以通过对标准归并排序算法进行简单修改来完成，其中我们为每个值分配一个权重，并计算 W[i]*W[j] 的总和，其中 i<j，A[i]>A[j]（当每个权重为1时，我们得到正常的计数）。我们不再将剩余元素的数量添加到计数中，而是将这些元素的权重之和乘以我们正在处理的右侧数组中元素的权重加入计数。

要使用此算法解决所提出的问题，只需创建一个两倍大小的数组，其中原始数组中的每个元素都被替换为两个元素（按排序顺序），其权重由概率给出。

- Nabb

---

我应该根据什么标准分配权重？如何对元素不确定的数组进行排序。您能否进一步阐述您的观点？ - Abhinav Chauhan

@AbhinavChauhan：请重新阅读最后一段——您需要创建一个不同的数组来运行加权逆序计数算法。 - Nabb

请告诉我另一件事.....我们创建另一个数组B，对于A中的每个位置'i'，我们在B中放置两个元素ai和(ai+x)，并分别赋予权重pi和(1-pi)....现在我们有了一个数组B。元素ei存在于B中的概率等于ei的权重。但是e1 (=a[1])和e2 (=a[1]+x)不能同时出现在A中。因此，与e1和e2的发生相应的两个事件不是独立的。但是您提出的解决方案（正确的）假定所有元素的发生事件彼此独立。这怎么可能？ - Abhinav Chauhan

@AbhinavChauhan：如果我正确理解你的问题，这应该是没问题的，因为期望的线性性质（E(X+Y) = E(X)+E(Y)）。 - Nabb

Answer 2

我已经留下了一条评论来解释这个问题，但是如果你使用一点数学，就可以进行O(1)的计算。我会为你省去这个过程，但是根据我的计算，n个整数数组中预期的逆序对数量为((n^2) - (n)) / 4。抱歉有太多括号，我只是想确保这完全清楚。如果您需要答案，我可以发布计算过程，但我认为如果您只需要答案，我会将其留出。

所以，尽管我的评论说得不对，但我记错了。它不是lg(n)。

- Dylan M.

---

答案取决于 x 和值 a1..an 和 p1..pn，它不总是 ((n^2)-(n))/4。例如，在 a[i]==i 且 p[i]==1 对于所有 i 的情况下，逆序对的期望数量为0，因为该数组以1的概率排序。我假设你回答的问题是类似于“洗牌数组中逆序对的期望数量是多少”，但这个数组没有被洗牌。 - Steve Jessop

哦，我好像误解了问题。我把它当作数组是随机生成的。对于我的误导性答案，我深表歉意。 - Dylan M.