由于我对Java很陌生，所以我正在努力优化程序的时间复杂度。我编写了一个简单的代码，它接受一个数组，并计算有多少对数字，数组中索引较低的元素大于索引较大的元素。
例如，如果您有数组：[9,8,12,14,10,54,41]，则将有 4 个这样的对：(9,8)、(12,10)、(14,10) 和 (54,41)。
我试图通过不仅仅是将每个元素与其他元素进行比较来优化代码。我的目标是n log n的时间复杂度。我还没有找到一种以更有效的方式编写此代码的方法。我希望我的问题很清楚。
代码(我省略了添加堆排序代码，因为它与我的问题无关。
import java.util.Scanner;
class Main4 {
static int n;
static int[] A;
// "A" is the input vector.
// The number of elements of A can be accessed using A.length
static int solve(int[] A) {
int counter = 0;
int[] B = new int[n];
B = A.clone();
heapSort(B);
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A.length; j++) {
while( B[j] == Integer.MIN_VALUE&&j+1<n) {
j=j+1;
}
if (A[i] != B[j]) {
counter++;
} else {
B[j] = Integer.MIN_VALUE;
break;
}
}
}
return counter; }
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int ntestcases = scanner.nextInt();
for (int testno = 0; testno < ntestcases; testno++) {
n = scanner.nextInt();
A = new int[n];
for (int i = 0; i < n; i++)
A[i] = scanner.nextInt();
System.out.println(solve(A));
}
scanner.close();
}
}
分而治之 1(类似合并排序)
将整个列表W分为两部分，L和早期长度相等的R。W的计数是
- 计数
L和R l和r分别属于L和R的l > r对数(l, r)。
第一个项目符号是递归。第二个项目符号不依赖于列表的顺序L和R.因此，您可以使用通过两个列表的单次传递对它们进行排序并确定结果(对排序R中所有较小的r进行排序L的第一个元素，现在可以增量计算第二个元素的计数，等等)。
时间复杂度由下式给出
T(n) = T(n/2) + T(n/2) + O(n log n)
我想这是O(n log n).无论如何，它比O(n*n)小得多.
你可以通过使用合并排序来改进它：你需要排序L，这可以通过合并排序LL和排序LR(这是递归步骤中L的两个部分)来实现。
分而治之2(快速排序)
选择一个元素m使较大和较小的元素的数量大致相同(中位数将是完美的，但随机选择的元素也可以使用)。
对数组进行一次单次传递，并计算有多少个小于m的元素。进行第二遍并计算(x, y)对，x放置在y的左侧，x >= m和m > y。
将列表拆分为两部分：e >= m元素和其余元素。冲洗并重复。
您正在寻找所有可能的对。
您可以从左到右检查以查找所有匹配项。这就是O(n^2)解决方案。正如 Arkadiy 在评论中建议的那样，此解决方案对于输入的最坏情况是可以的。
我想出了一个想法，您可能希望按排序顺序存储元素并保留原始的未排序数组。
您保留原始数组并构建二叉搜索树。您可以及时找到具有原始索引i的元素O(lgn)并在O(lgn)中删除它，这很棒。您还可以确定小于第 i 个元素的值的数量，但附加成本很小。
为了能够计算小于的元素，每个节点必须存储其子节点的数量 + 1。删除时，只需在下降过程中减少每个节点中的子节点数。插入时，您将在向下的过程中增加每个节点中的子节点数。当您搜索节点时，您将根节点的值存储在变量和
- 当你去找对孩子时什么都不做， 当你
- 转到左边的孩子时，从你的变量中减去孩子的数量
停止(找到节点)后，减去右子级的值(如果没有右子级，则为 0)并递减该值。
从左到右遍历原始数组。在每一步中，您都可以在树中找到元素，并计算树中有多少较小的元素。您知道有多少比当前元素小，并且您还知道树中的所有元素都具有比当前元素更大的索引，当前元素知道您可以将其与多少个元素配对！计算对数后，从树中删除此元素。你这样做n次。从树中查找和删除是O(lgn)==O(nlgn)时间复杂度！总时间O(nlgn + nlgn) = O(nlgn)！！
算法导论(第3版)第12章深入解释了如何实现BST。您还可以在互联网上找到许多用图片解释它的资源。