在复杂性分析中，用新数组覆盖现有数组是否会花费额外的时间或内存？

Question

假设我们有一个函数，它接受一个已排序的整数数组作为参数，并将返回一个新数组，其中包含输入数组中最常出现的数字；换句话说，该函数返回数组的众数：

// Example input: [1, 2, 2, 3, 3, 3, 4]
function getArrayMode(array) {
    let modes = [];
    let currentStreak = 0;
    let bestStreak = 0;
    let previousNumber = null;
    for (const number of array) {
        if (number === previousNumber) currentStreak++;
        else currentStreak = 1;
        if (currentStreak === bestStreak) {
            modes.push(number);
        } else if (currentStreak > bestStreak) {
            modes = [number]; // What impact does this have?
            bestStreak = currentStreak;
        }
        previousNumber = number;
    }
    return modes;
}

我相信这个函数的时间复杂度是 O(n)，空间复杂度是 O(1) 当不考虑输出数组时。但是重新分配一个新数组

modes = [number]

实际上会影响Javascript中的复杂性分析吗？如果我们对输出数组进行计数，事情会改变吗？当我们对数组执行此操作时，幕后发生了什么？

Answer 1

重新分配一个新的数组 models = [number] 实际上会影响 Javascript 中的复杂性分析吗？当我们对数组执行此操作时，幕后发生了什么？

在此赋值之前

modes

引用的数组将被该赋值孤立，从而受到垃圾回收的影响。在分析空间复杂度时，我们可能会忽略这种孤立的内存。如果我们这样做的话，我们会得到相同的空间复杂度分析：

nodes.length = 0; // Clear the array
modes.push(number);

因此，我们应该考虑 

modes

在执行此代码期间引用的 maximum 数组大小。

如果我们对输出数组进行计数，事情会改变吗？

是的，但是在分析中不计算输出数组是不常见的：即使它是输出，它仍然是算法必须分配的空间，因此会产生您想要注意的内存影响。不考虑该记忆是没有意义的。

还要认识到，在某些情况下，

modes

使用的内存可能会超过输出所需的内存。以此为例输入：

[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 8]

该算法将填充 

modes

以最终包含

[1, 2, 3, 4, 5, 6, 7]

，但随后会重新分配一个新数组

[8]

，这将是最终结果。该算法分配了内存来存储中间数组，但输出所需的内存要少得多。一般来说，存在“最佳”情况（就输出大小而言），其中输出的空间复杂度为 O(1)，但辅助空间为 O(𝑛)。对于这些情况，我们不能得出结论：空间复杂度——

当不考虑输出数组时

——是 O(1)。 分析空间复杂度的标准方法是以与算法分配的任何其他内存相同的方式对待分配用于表示输出的内存。

考虑到这一点，最坏情况的空间复杂度是 O(𝑛)，而最好情况的空间复杂度是 O(1)——例如，当所有输入值的频率不同并且输入已排序时。