这个算法的运行时和空间复杂度是什么以及为什么

Question

在练习一些算法时,我遇到了以下问题,我无法弄清楚时间和空间的复杂程度.

问题: 从数组中打印成对的num,其总和为k.例如

int[] arr =  new int[]{1, 7, 2, 3, 4};
int k = 4;
findSum(arr, k);

将输出

Pair: 1, 3

我的问题: 下面解决方案的运行时和空间复杂度是多少？

Java示例如下:

private void findSum(int[] arr, int k) {
    if (arr == null || arr.length < 2)
        throw new RuntimeException();

    Arrays.sort(arr);
    int i = 0; int j = arr.length -1;
    while (i < j) {
        int sum = arr[i] + arr[j];
        if (sum == k)
        {
            System.out.println("Pair: " + arr[i] + ", " + arr[j]);
            i++;
        } else if (sum > k) {
            j--;
        } else {
            i++;
        }
    }
}

Answer 1

由于您首先对数组进行排序,因此需要O(n log n) - n是数组的大小

但是while循环最多需要O(n).因此,总计:O(n log n + n)= O(n log n).

关于空间复杂度,该数组采用O(n)+ 2个常数变量,它仍然是O(n).

注意:Java的Arrays.sort使用修改后的mergesort - O(n log n).