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 中所做的一切，时间复杂度在这里很重要 c

Answer 1

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