使用分桶计数反转
Counting inversion using bucketing
我正在尝试计算数组中的倒置（如果 a[i] > a[j] 且 i < j，则两个元素 a[i] 和 a[j] 形成倒置）。我知道在 O(n^2) 中使用蛮力和在 O(nlgn) 中使用分而治之可以很容易地解决这些问题。
我的问题是，是否可以使用一种形式的分桶技术在了解数据的情况下实现 O(n) 的效率。例如，我已经知道数组是 1-32 的排列，因此最大元素是 32（这意味着我们可以用分桶做一些事情）。
我一直在思考这个问题，并注意到如果我们在一个桶中插入一个元素，那么在插入时所有大于它的桶的总和就是它的反转计数。但是如果我们每次都添加每个桶中的元素数量，那么它会导致我失去 O(n) 的效率。关于如何保持计数以消除此惩罚的任何建议。
请注意排列可以是任意长度，但在执行过程中我们知道排列中元素的数量。因此 "n" 的值在执行期间是已知的，并且排列由从“1”到 "n".
的元素组成
排序：可以在 O(n) 时间复杂度内对这个数据集进行排序，因为我们可以创建 32 个桶，并且我们知道每个桶只有一个元素。因此，对于此特定示例，桶排序的效率为 O(n + M) 为 O(n + 1) = O(n)。
根据 http://arxiv.org/pdf/1503.01192.pdf，"well known" 你找不到比 O(n log n) 更有效的倒置次数。
我正在尝试计算数组中的倒置（如果 a[i] > a[j] 且 i < j，则两个元素 a[i] 和 a[j] 形成倒置）。我知道在 O(n^2) 中使用蛮力和在 O(nlgn) 中使用分而治之可以很容易地解决这些问题。
我的问题是，是否可以使用一种形式的分桶技术在了解数据的情况下实现 O(n) 的效率。例如，我已经知道数组是 1-32 的排列，因此最大元素是 32（这意味着我们可以用分桶做一些事情）。
我一直在思考这个问题，并注意到如果我们在一个桶中插入一个元素，那么在插入时所有大于它的桶的总和就是它的反转计数。但是如果我们每次都添加每个桶中的元素数量，那么它会导致我失去 O(n) 的效率。关于如何保持计数以消除此惩罚的任何建议。
请注意排列可以是任意长度，但在执行过程中我们知道排列中元素的数量。因此 "n" 的值在执行期间是已知的，并且排列由从“1”到 "n".
的元素组成排序：可以在 O(n) 时间复杂度内对这个数据集进行排序，因为我们可以创建 32 个桶，并且我们知道每个桶只有一个元素。因此，对于此特定示例，桶排序的效率为 O(n + M) 为 O(n + 1) = O(n)。
根据 http://arxiv.org/pdf/1503.01192.pdf，"well known" 你找不到比 O(n log n) 更有效的倒置次数。