新手辨别 space 复杂性的问题

Question

谁能解释一下为什么这个算法的 space 复杂度是 O(n) 而不是 O(1)？

function subtotals(array) {
    var subtotalArray = Array(array.length);
    for (var i = 0; i < array.length; i++) {
        var subtotal = 0;
        for (var j = 0; j <= i; j++) {
            subtotal += array[j];
        }
        subtotalArray[i] = subtotal;
    }
    return subtotalArray;
}

Answer 1

您正在为 array 参数中的每个项目在 subtotalArray 中创建一个新元素。因此，如果输入数组中有 1000 个项目，输出数组将需要一定数量的内存，比方说 X。如果输入数组中有 100,000 个项目，输出数组将需要 100* X 内存，或者大约。

（还有在每次迭代中创建的 subtotal 数字）