2

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

问题： 从数组中打印出加起来为 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++;
        }
    }
}
4

2 回答 2

8

由于您首先对数组进行排序，因此需要 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 使用修改后的合并排序——O (n log n)。

于 2013-10-09T04:37:22.523 回答
1

设 n 为数组的大小：

空间复杂度：O(n) - 一个长度为 n + 几个变量的数组。
时间复杂度：O(n logn) - 排序需要 O(n logn) 并且 while 循环将进行 n 次迭代。为了证明这一点，请考虑 ji 的值。它从 n-1 开始，每次迭代后减一。当 i=j 时，循环停止，换句话说，当 ji=0 时。

于 2013-10-09T04:56:45.120 回答