performance - 这个算法的运行时间和空间复杂度是多少，为什么

Question

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

问题:打印数组中加起来等于 k ​​之和的 nums 对。例如

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 使用 modified mergesort -- O(n log n)。