这是使用HeapSort进行的O（nlogn）的时间复杂度

Question

这是O（nlogn）时间的时间复杂度吗？如果没有，我该如何解决]

目标：使用HeapSort应该使用每个数组中的1个数字来查找和对，以找到a + b = c（给定）

基本HeapSort排序功能

boolean SumPairs(int[] Arr1, int[] Arr2, int p) {

    heapSort(Arr2, p);

    int target = 0;

    for (int i = 0; i < Arr1.length; i++) {
        target = p - Arr1[i];
    if (BinarySearch(Arr2, target) != -1)
        return true;
  }
    return false;
 }

Answer 1

正确实施堆排序的平均时间复杂度为O（NlogN）;参见https://en.wikipedia.org/wiki/Heapsort。

正确实施的二进制搜索的平均时间复杂度为O（logN）；参见https://en.wikipedia.org/wiki/Binary_search_algorithm

因此，假设您正在调用的方法已正确实现，则每个调用的方法平均时间复杂度为O(NlogN) + (O(N) * O(logN))。减少到O(NlogN)。