在著名程序“一维数组的运行求和”的空间复杂度分析中,我们发现无论是在同一个数组中返回解还是在新创建的数组中返回解,空间复杂度都是 O(N)。
即使程序指定返回数组作为输出,为什么这两种情况在空间复杂度分析上没有区别?
方法 1:以新数组作为输出的解决方案
public static int[] runningSum(int[] nums) {
int[] sum= new int[nums.length];
sum[0]=nums[0];
for(int i=1;i<nums.length;i++){
sum[i]= nums[i]+sum[i-1];
}
return sum;
}
方法2:以输入数组作为输出的解决方案
public static int[] runningSumReturnSameArray(int[] nums) {
for(int i=1; i< nums.length;i++){
nums[i]=nums[i-1]+nums[i];
}
return nums;
}
方法 1 和方法 2 在空间上有差异,因此我期望它在各自的空间复杂度上有差异。
两者具有相同的空间复杂度 O(n)。
空间复杂度:是相对于输入大小所需的内存空间量。
对于方法 1: 空间复杂度为 O( n )
意味着我们在这个大小为 n 的函数中添加内存空间;其中 n 是输入的大小
对于方法 2: 空间复杂度为 O( 1 )
因为无论输入大小如何,函数空间使用量都保持不变。
我希望这有帮助🙏