我几天来一直在努力想出遵循下面伪代码的代码来计算未排序的排列数列表的反转次数。我需要算法在 O(nlogn) 时间内运行，但我只能在 O(n^2logn) 时间内想到解决方案。
更具体地说，我想知道如何通过不使用嵌套 for 循环来加速第二步。我知道还有其他有效的算法(即合并排序)可以工作，但我需要遵循伪代码的步骤。
Instance: An array A[1] . . . A[n], a permutation of n numbers 1, . . . , n
Question: Calculate vector B[j] = |{A[i] : j > i and A[i] > A[j]}| (the same as
B[j] = |{i : j > i and A[i] > A[j]}|) B[j] is the number of element
larger than A[j] to the left of A[j] in t the array A. In other words,
the sum of the elements in B is equal to the number of inversions in
the permutation A[1] . . . A[n].
(1) Initialize B[i] to 0.
(2) For each even A[j] find elements with indices smaller than j that are by one larger
than A[j]: increase B[j] by the number of such elements;
(3) Divide each A[i] by 2 (in the integer sense);
(4) Stop when all A[i] are 0.
以下是我迄今为止想到的代码:
long long numInversions = 0;
// number of elements that are zero in the array
unsigned int zeros = 0;
do {
// solution will need to replace this nested
// for loop so it is O(n) not O(n^2)
for (int i = 0; i < permNumber; i++){
// checks if element is even
if(array[i] % 2 == 0){
for (int j = i; j >= 0; j--){
if (array[j] == array[i] + 1){
numInversions++;
}
}
}
}
// resets value of zeros for each pass
zeros = 0;
for (int k = 0; k < permNumber; k++){
array[k] = array[k] / 2;
if (array[k] == 0)
zeros++;
}
} while(zeros != permNumber);
注意:算法应返回列表中的反转数，一个标量。伪代码要求一个数组，但最终对数组的元素求和以计算反转计数。
Example: Consider a permutation (2, 3, 6, 1, 3, 5) with six inversions. The
above algorithm works as follows:
2 4 6 1 3 5 (no pairs) ÷2
1 2 3 0 1 2 1 = 0: one '1' to left, 2: one 3 to left ÷2
0 1 1 0 0 1 1 = 0: two '1's to left, 0: two '1's to left ÷2
0 0 0 0 0 0 total: 6 pairs
最佳答案
这是一个非常聪明的算法——在每次迭代中，它都会计算除以二所删除的反转......尽管没有必要为 B 使用数组，因为所有你要做的就是添加元素，然后将它们相加。您可以只保留一个运行总和。
无论如何...为了加快步骤 (2)，您可以使用另一个数组 C[v] 来记住 A 中所有奇数值的计数，像这样:
Step 2:
Initialize all C[v] to 0
For i = 1 to n: //0 to n-1 if you're using 0-based arrays
if A[i] is even then:
B[i] += C[A[i]+1]
else:
C[A[i]] += 1
关于c++ - 不使用合并排序的倒置计数算法 (c++)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48977484/