数组重赋值的时空复杂度影响及JavaScript底层机制分析

1. 在复杂度分析场景下，用新数组覆盖已有数组是否会额外消耗时间或内存？ #

• 时间消耗：新数组赋值（如arr = [x]）属于O(1)的常数时间操作，仅需创建包含指定元素的新数组，无需遍历或复杂计算，不会改变整体时间复杂度的阶数。
• 内存消耗：赋值后原数组会被标记为垃圾回收对象，但在回收完成前会短暂存在两份内存占用。不过复杂度分析关注的是最坏情况下的峰值内存：
  • 若新数组规模远小于原数组，峰值内存由原数组的最大尺寸决定；
  • 若频繁替换同规模数组，峰值内存也不会超过该规模的常量倍数，因此通常不会改变空间复杂度的阶数。

2. 针对获取有序数组众数的JavaScript函数的疑问 #

先贴出目标函数代码：

// 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;
}

关于modes = [number]对复杂度分析的影响 #

你的初始判断是正确的：不考虑输出数组时，函数时间复杂度为O(n)、空间复杂度为O(1)。modes = [number]是常数时间操作，不会增加时间复杂度的阶数；同时，因为不计入输出数组的空间，该操作也不会引入额外的线性空间，所以不会改变空间复杂度的结论。

计入输出数组时的复杂度变化 #

• 时间复杂度：仍为O(n)，所有操作都在一次线性遍历中完成，每个步骤都是常数时间。
• 空间复杂度：变为O(k)（k为众数的个数），最坏情况下k可以达到O(n)（比如数组中所有元素互不相同，此时每个元素的出现次数都是1，modes会包含所有元素），因此最坏空间复杂度为O(n)。

该操作在JavaScript中的底层逻辑 #

1. 执行modes = [number]时，JS引擎会在堆内存中创建一个新的数组对象：若number是基本类型（如数字、字符串），则直接存储其值；若为引用类型，则存储指向该对象的引用。
2. 原modes数组对象如果没有其他变量引用它，会被标记为可垃圾回收对象，等待JS引擎的垃圾回收线程在合适时机释放其占用的内存。
3. 变量modes本身是存储在调用栈中的引用指针，赋值操作会将这个指针更新为指向新创建的数组对象。

内容的提问来源于stack exchange，提问作者Ginger and Lavender