在练习一些算法时,我遇到了以下问题,我无法弄清楚时间和空间的复杂度。
问题: 打印数组中加起来等于 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++;
}
}
}
最佳答案
由于您首先对数组进行排序,因此需要 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)。
关于performance - 这个算法的运行时间和空间复杂度是多少,为什么,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19263192/