Java

Question

我知道时间复杂度是O(n)。但是 这段代码的 space 复杂度是多少？ 意思是在最坏的情况下，需要的最大 space 数量是多少？我的猜测是它是 O(1)，因为数组已经有一个恒定数量的 space，因此 space 不会递增。

代码：

public int[] countBits(int num) {
        int[] res = new int[num+1];

        for (int i = 0; i<num+1; i++){
            res[i] = Integer.bitCount(i);
        }

        return res;
    }

Answer 1

Space 算法的复杂性 是输入大小的总 space，包括辅助 space 和 space 由输入使用。

此外，辅助Space是算法使用的临时space。

在您的示例中，在计算创建数组 new int[num+1] 需要多少存储空间时包括输入（ 传递的参数 num）。同样，for-loop 会更大。

作为结论，Space 复杂度为 O(n)，时间复杂度为 O(n).

Java - Space for 循环中数组的复杂性

Java - Space complexity with array in for loop

space-complexity