为何空间复杂度分析不含输出空间？一维数组前缀和案例解惑

首先得明确空间复杂度的核心定义：我们常说的空间复杂度，默认分两种——额外空间复杂度和总空间复杂度。

关于输出空间不算入额外空间的原因 #

额外空间复杂度衡量的是算法除了输入数据和题目要求必须输出的结果空间之外，额外开辟的存储空间。输出空间是问题本身要求你必须生成的结果载体，不管你用新数组还是复用原数组，这部分空间是完成任务的必要开销，不是算法额外消耗的，所以不会算进额外空间复杂度里。

两种实现的空间复杂度分析 #

先看你的两段代码：

方法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;
    }

这段代码里，额外开辟了一个长度为N的sum数组作为输出，所以额外空间复杂度是O(N)；如果算总空间复杂度（输入+输出+额外），输入数组是O(N)，输出数组是O(N)，总空间还是O(N)（大O表示法只看量级，常数系数忽略）。

方法2：复用原数组当输出

public static int[] runningSumReturnSameArray(int[] nums) {
        for(int i=1; i< nums.length;i++){
            nums[i]=nums[i-1]+nums[i];
        }
        return nums;
    }

这段代码没有额外开辟任何数组，只是在原输入数组上修改，所以额外空间复杂度是O(1)；但总空间复杂度还是O(N)，因为输入数组本身就是O(N)的空间。

为什么两种情况的空间复杂度会被认为相同？ #

你觉得两种情况空间复杂度没差异，大概率是因为你看到的分析用的是总空间复杂度。总空间复杂度里，不管你是新开辟输出数组还是复用输入数组，整体空间量级都是O(N)——方法1是输入+输出两个O(N)，加起来还是O(N)；方法2是输入一个O(N)，自然也是O(N)。大O表示法只关注随着输入规模增长时的空间增长趋势，不会区分常数倍的差异，所以两种情况的总空间复杂度都是O(N)。

如果是看额外空间复杂度，那两种情况是有区别的：方法1是O(N)，方法2是O(1)，这也是方法2更优的地方——它的额外空间开销是常数级的。

内容的提问来源于stack exchange，提问作者Suman