c - 用于查找对的数组 O(nlogn) 复杂度方法中的元素

Question

好的，我一直被这里的复杂性所困扰。有一个元素数组，比如说A[n]。需要找到所有对以便A[i]>A[j]和也i < j。

因此，如果是{10, 8, 6, 7, 11}，则对将是(10,8) (10, 6), (10,7) and so on...

我在 nlogn 时间内进行了合并排序，然后在 nlogn 中再次对整个数组进行二进制搜索，以获取排序数组中元素的索引。

所以sortedArray={6 7 8 10 11}和index={3 2 0 1 4}

无论我尝试什么，n^2当我开始循环比较时，我都会在复杂性中再次获得时间。我的意思是，如果我从第一个元素（即 10）开始，则index[2]意味着比它少 2 个元素。因此，如果index[2]<index[i]那时它们可以被接受，但这会增加复杂性。有什么想法吗？我不想要代码，只是在正确方向上的提示会有所帮助。

谢谢。我在C中所做的一切和时间复杂度在这里都很重要

Answer 1

您不能在 under 中执行此操作O(N^2)，因为当原始数组按降序排序时算法将产生的对数是N(N-1)/2。你根本无法及时产生O(N^2)结果O(N*LogN)。

Answer 2

结果由 O(n^2) 个元素组成，因此任何迭代所有对的尝试都是 O(n^2)。